
Bit manipulation basics 

Code 
01: int setBit(int x, unsigned char position)
bits.stephanbrumme.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 bitwise 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 CPU cycles (full optimization, lower values are better) 
Assembler Output 
setBit:
bits.stephanbrumme.com

Download  The full source code including a test program is available for download. 
References 
none 
More Twiddled Bits 
... or go to the index 