How to Unset a Specific Bit in an Integer

How to unset a specific bit in an integer

Assuming that you are indexing bits from the right, this should work to unset a particular bit in value:

int mask = 1 << bitIndex;
value &= ~mask;

You can set the bit using similar code:

value |= mask;

where mask is as before. (This assumes that bit indexing starts at 0.)

How to remove a bit from an int?

wallsWithRightWallRemoved = walls & 0x0111;

Or will set bits that are in either. And will unset bits that are 0 in either, which is what you want to do.

How to set/unset a bit at specific position of a long?

To set a bit, use:

x |= 0b1; // set LSB bit
x |= 0b10; // set 2nd bit from LSB

to erase a bit use:

x &= ~0b1; // unset LSB bit (if set)
x &= ~0b10; // unset 2nd bit from LSB

to toggle a bit use:

x ^= 0b1;

Notice I use 0b?. You can also use any integer, eg:

x |= 4; // sets 3rd bit
x |= 0x4; // sets 3rd bit
x |= 0x10; // sets 9th bit

However, it makes it harder to know which bit is being changed.

Using binary allows you to see which exact bits will be set/erased/toggled.

To dynamically set at bit, use:

x |= (1 << y); // set the yth bit from the LSB

(1 << y) shifts the ...001 y places left, so you can move the set bit y places.

You can also set multiple bits at once:

x |= (1 << y) | (1 << z); // set the yth and zth bit from the LSB

Or to unset:

x &= ~((1 << y) | (1 << z)); // unset yth and zth bit

Or to toggle:

x ^= (1 << y) | (1 << z); // toggle yth and zth bit

C# How to remove the n-th bit in integer?

No problem, just decompose the number into the "upper part" and the "lower part", and put them together without the middle bit that now disappeared.

Not tested:

uint upper = x & 0xFFFFFFF0;
uint lower = x & 7;
return (upper >> 1) | lower;

More generally: (also not tested)

uint upper = x & (0xFFFFFFFE << n);
uint lower = x & ((1u << n) - 1);
return (upper >> 1) | lower;

Set and Unset a specific bit in a 64-bit integer

You can marginally speed up compilation time by getting rid of the macros, but that's about it. Bit twiddling is fast enough so it shouldn't be an issue.

This is the idiomatic way of doing it, I wouldn't change a thing.

How do I set, clear, and toggle a single bit?

Setting a bit

Use the bitwise OR operator (|) to set a bit.

number |= 1UL << n;

That will set the nth bit of number. n should be zero, if you want to set the 1st bit and so on upto n-1, if you want to set the nth bit.

Use 1ULL if number is wider than unsigned long; promotion of 1UL << n doesn't happen until after evaluating 1UL << n where it's undefined behaviour to shift by more than the width of a long. The same applies to all the rest of the examples.

Clearing a bit

Use the bitwise AND operator (&) to clear a bit.

number &= ~(1UL << n);

That will clear the nth bit of number. You must invert the bit string with the bitwise NOT operator (~), then AND it.

Toggling a bit

The XOR operator (^) can be used to toggle a bit.

number ^= 1UL << n;

That will toggle the nth bit of number.

Checking a bit

You didn't ask for this, but I might as well add it.

To check a bit, shift the number n to the right, then bitwise AND it:

bit = (number >> n) & 1U;

That will put the value of the nth bit of number into the variable bit.

Changing the nth bit to x

Setting the nth bit to either 1 or 0 can be achieved with the following on a 2's complement C++ implementation:

number ^= (-x ^ number) & (1UL << n);

Bit n will be set if x is 1, and cleared if x is 0. If x has some other value, you get garbage. x = !!x will booleanize it to 0 or 1.

To make this independent of 2's complement negation behaviour (where -1 has all bits set, unlike on a 1's complement or sign/magnitude C++ implementation), use unsigned negation.

number ^= (-(unsigned long)x ^ number) & (1UL << n);

or

unsigned long newbit = !!x;    // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);

It's generally a good idea to use unsigned types for portable bit manipulation.

or

number = (number & ~(1UL << n)) | (x << n);

(number & ~(1UL << n)) will clear the nth bit and (x << n) will set the nth bit to x.

It's also generally a good idea to not to copy/paste code in general and so many people use preprocessor macros (like the community wiki answer further down) or some sort of encapsulation.

Simple way to set/unset an individual bit

Sure! It would be more obvious if you expanded the |= and &= in your code, but you can write:

nbyte = (nbyte & ~(1<<4)) | (bit4Set<<4);

Note that bit4Set must be zero or one —not any nonzero value— for this to work.

Set all meaningful unset bits of a number

If you need to do integer arithmetics and count bits, you'd better count them properly, and avoid introducing floating point uncertainty:

unsigned x=0;
for (;n;x++)
    n>>=1;
...

(demo)

The good news is that for n<=1E18, x will never reach the number of bits in an unsigned long long. So the rest of you code is not at risk of being UB and you could stick to your minus 1 approach, (although it might in theory not be portable for C++ before C++20) ;-)

Btw, here are more ways to efficiently find the most significant bit, and the simple log2() is not among them.

How to unset N right-most set bits

For Intel x86 CPUs with BMI2, pext and pdep are fast. AMD before Zen3 has very slow microcoded PEXT/PDEP (https://uops.info/) so be careful with this; other options might be faster on AMD, maybe even blsi in a loop, or better a binary-search on popcount (see below).

Only Intel has dedicated hardware execution units for the mask-controlled pack/unpack that pext/pdep do, making it constant-time: 1 uop, 3 cycle latency, can only run on port 1.

I'm not aware of other ISAs having a similar bit-packing hardware operation.

---

pdep basics: pdep(-1ULL, a) == a. Taking the low popcnt(a) bits from the first operand, and depositing them at the places where a has set bits, will give you a back again.

But if, instead of all-ones, your source of bits has the low N bits cleared, the first N set bits in a will grab a 0 instead of 1. This is exactly what you want.

uint64_t unset_first_n_bits_bmi2(uint64_t a, int n){
    return _pdep_u64(-1ULL << n, a);
}

-1ULL << n works for n=0..63 in C. x86 asm scalar shift instructions mask their count (effectively &63), so that's probably what will happen for the C undefined-behaviour of a larger n. If you care, use n&63 in the source so the behaviour is well-defined in C, and it can still compile to a shift instruction that uses the count directly.

On Godbolt with a simple looping reference implementation, showing that they produce the same result for a sample input a and n.

GCC and clang both compile it the obvious way, as written:

# GCC10.2 -O3 -march=skylake
unset_first_n_bits_bmi2(unsigned long, int):
        mov     rax, -1
        shlx    rax, rax, rsi
        pdep    rax, rax, rdi
        ret

(SHLX is single-uop, 1 cycle latency, unlike legacy variable-count shifts that update FLAGS... except if CL=0)

So this has 3 cycle latency from a->output (just pdep)

and 4 cycle latency from n->output (shlx, pdep).

And is only 3 uops for the front-end.

---

A semi-related BMI2 trick:

pext(a,a) will pack the bits at the bottom, like (1ULL<<popcnt(a)) - 1 but without overflow if all bits are set.

Clearing the low N bits of that with an AND mask, and expanding with pdep would work. But that's an overcomplicated expensive way to create a source of bits with enough ones above N zeros, which is all that actually matters for pdep. Thanks to @harold for spotting this in the first version of this answer.

---

Without fast PDEP: perhaps binary search for the right popcount

@Nate's suggestion of a binary search for how many low bits to clear is probably a good alternative to pdep.

Stop when popcount(x>>c) == popcount(x) - N to find out how many low bits to clear, preferably with branchless updating of c. (e.g. c = foo ? a : b often compiles to cmov).

Once you're done searching, x & (-1ULL<<c) uses that count, or just tmp << c to shift back the x>>c result you already have. Using right-shift directly is cheaper than generating a new mask and using it every iteration.

High-performance popcount is relatively widely available on modern CPUs. (Although not baseline for x86-64; you still need to compile with -mpopcnt or -march=native).

Tuning this could involve choosing a likely starting-point, and perhaps using a max initial step size instead of pure binary search. Getting some instruction-level parallelism out of trying some initial guesses could perhaps help shorten the latency bottleneck.

Set a specific bit in an int

If you have an int value "intValue" and you want to set a specific bit at position "bitPosition", do something like:

intValue = intValue | (1 << bitPosition);

or shorter:

intValue |= 1 << bitPosition;

If you want to reset a bit (i.e, set it to zero), you can do this:

intValue &= ~(1 << bitPosition);

(The operator ~ reverses each bit in a value, thus ~(1 << bitPosition) will result in an int where every bit is 1 except the bit at the given bitPosition.)

---

Related Topics