# Bit manipulation basics

Code
``` 01: int setBit(int x, unsigned char position) 02: { 03:   int mask = 1 << position; 04:   return x | mask; 05: } 06: 07: int clearBit(int x, unsigned char position) 08: { 09:   int mask = 1 << position; 10:   return x & ~mask; 11: } 12: 13: int modifyBit(int x, unsigned char position, bool newState) 14: { 15:   int mask = 1 << position; 16:   int state = int(newState); // relies on true = 1 and false = 0 17:   return (x & ~mask) | (-state & mask); 18: } 19: 20: int flipBit(int x, unsigned char position) 21: { 22:   int mask = 1 << position; 23:   return x ^ mask; 24: } 25: 26: bool isBitSet(int x, unsigned char position) 27: { 28:   x >>= position; 29:   return (x & 1) != 0; 30: } ``` bits.stephan-brumme.com

Explanation The shown operation are the 101 of bit manipulation. If you have at least an introductory knowledge

These basic algorithms rely on a mask representing the position of the bit to be changed.
This mask is created by left shifting 1 (line 3, line 9 and line 15). Depending on the compiler/system,
position is limited to 15, 31 or 63, although − to simplify things − this restriction is not checked by the code.

Here are the basics of boolean algebra:

0 OR 0 → 0
0 OR 1 → 1
1 OR 0 → 1
1 OR 1 → 1

0 AND 0 → 0
0 AND 1 → 0
1 AND 0 → 0
1 AND 1 → 1

0 XOR 0 → 0
0 XOR 1 → 1
1 XOR 0 → 1
1 XOR 1 → 0

Whenever a bit needs to be set independent of its former state (setBit), OR comes in handy:

input OR 1 → 1
input OR 0 → input

That means, a mask which is 1 for all bits to be set and 0 for all other bits fulfills our purposes (line 3, line 4).

For clearing a bit (clearBit), AND has to be chosen because:

input AND 0 → 0
input AND 1 → input

This time, the mask must be 0 for all cleared bits and 1 for bits keeping their former state.
Line 10 uses the bit-wise negation to flip all bits of the mask accordingly.

Flipping a bit (flipBit) is the domain of XOR:

input XOR 1 → opposite of input
input XOR 0 → input

That code looks almost identical to OR.

Last but not least, querying a single bit (isBitSet) can be implemented very similiar to clearing a single bit:
create a mask, negate it, check for 0. When looking at the assembler code, I changed to a faster way
by shifting right the value to move the interesting bit to position 0 (line 28).
Then, AND 1 clears all but this bit. Checking for 0 returns the desired result (line 29).
In C++, bool is typically an integer where false → 0 and true → 1.
That means, just two assembler instructions are required for isBitSet.

Note: Visual C++ provides the _bittest, _bittestandset, _bittestandreset and _bittestandcomplement intrinsics
which might generate a single assembler instruction (if available) for these operations and are never slower.
Note, too: Even though these intrinsics are not supported by all compilers, the shown assembler code will probably
be heavily optimized, too: if the shift is constant, the mask is precomputed during compile time
and just one instruction is left.

Restrictions • integer based
• no range checking for position

help me to pay
my server bills

Performance • constant time, data independent

+ Intel® Pentium™ D:
setBit: ≈ 2.5 cycles per number
clearBit: ≈ 3.5 cycles per number
modifyBit: ≈ 6.5 cycles per number
flipBit: ≈ 2.5 cycles per number
isBitSet: ≈ 3 cycles per number

+ Intel® Core™ 2:
setBit: ≈ 1 cycle per number
clearBit: ≈ 1.5 cycles per number
modifyBit: ≈ 3.5 cycles per number
flipBit: ≈ 1 cycles per number
isBitSet: ≈ 2 cycles per number

+ Intel® Core™ i7:
setBit: ≈ 1 cycle per number
clearBit: ≈ 1.33 cycles per number
modifyBit: ≈ 3 cycles per number
flipBit: ≈ 1 cycles per number
isBitSet: ≈ 2 cycles per number

CPU cycles
(full optimization,
lower values are better)

Assembler Output
``` setBit: compiler: VC 2008 in: edx ← x, cl ← position out: eax → result 01:   mov eax, 1 02:   shl eax, cl 03:   or  eax, edx clearBit: compiler: VC 2008 in: edx ← x, cl ← position out: eax → result 01:   mov eax, 1 02:   shl eax, cl 03:   not eax 04:   and eax, edx modifyBit: compiler: VC 2008 in: esi ← x, cl ← position, dl ← newState out: eax → result temp: esi 01:   ; mask = 1 << position 02:   mov eax, 1 03:   shl eax, cl 04:   ; state = int(newState) 05:   movzx ecx, dl 06:   neg ecx 07:   ; return (x & ~mask) | (-state & mask) 08:   and ecx, eax 09:   not eax 10:   and eax, esi 11:   or eax, ecx flipBit: compiler: VC 2008 in: edx ← x, cl ← position out: eax → result 01:   mov eax, 1 02:   shl eax, cl 03:   xor eax, edx isBitSet: compiler: VC 2008 in: eax ← x, cl ← position out: eax → result 01:   shr eax, cl 02:   and eax, 1 ``` bits.stephan-brumme.com