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
about bit twiddling, you should skip this page.

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

These ads
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
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
setBit:
01:   mov eax, 1
02:   shl eax, cl
03:   or  eax, edx

clearBit:
01:   mov eax, 1
02:   shl eax, cl
03:   not eax
04:   and eax, edx

modifyBit:
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:
01:   mov eax, 1
02:   shl eax, cl
03:   xor eax, edx

isBitSet:
01:   shr eax, cl
02:   and eax, 1
 bits.stephan-brumme.com

Download The full source code including a test program is available for download.

References none

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index