Bit Manipulation Hacks
This wiki assumes familiarity with binary numbers, logic gates and the two's complement system.
In this wiki, we shall discuss a number of one liners that help us solve simple arithmetic problems in binary numbers. They are often found to be very useful (and quick) in larger programs.
Because of the way numbers are represented in computers, these one liners are not only handy for the programmer but also very fast in execution.
Contents
Bitwise operators
The Bitwise operators constitute the standard operators from boolean algebra along with the shift operators.
 Bitwise AND (
&
) Apply AND bit by bit on the operand integers.  Bitwise OR (

) Apply OR bit by bit on the operand integers.  Bitwise XOR (
^
) Apply XOR bit by bit on the operand integers.  Bitwise NOT (
~
) Flip all bits of the operand  Left Shift (
<<
) Shift the bits to the left by the specified amount, discarding bits on the extreme left, if necessary. This is equivalent to multiplying by \(2^n\)  Right Shift (
>>
) Shift the bits to the right by the specified amount, discarding bits on the extreme right, if necessary. This is equivalent to integer division by \(2^n\)
Is this number odd?
1 

This is straightforward. If a number is odd, its binary expansion ends in 1
. When the number is subjected to bitwise &
, all the other bits except the least significant bit remain.
1 2>>> odd(10) 0
Explanation
10 1 0 1 0 1 0 0 0 1 10&1 0 0 0 0
Is that bit set?
We could easily extend the previous idea to check if the nth bit is set in an integer. The following returns a nonzero integer when the nth bit is set.
1 

We shift the 1
to the appropriate place and do the &
operation.
1 2>>> isNthBitSet(2,11) 0
Explanation
11 1 0 1 1 1 << 2 0 1 0 0 11 & (1 << 2) 0 0 0 0
Set that bit
To set a bit, we shift an 1
under the necessary place and apply bitwise OR.
1 

This returns the given integer with it's nth bit set.
1 2>>> setNthBit(2,10) 14
Explanation
10 1 0 1 0 1 << 2 0 1 0 0 10  (1 << 2) 1 1 1 0 Clearly enough.
0b1110
is the same as 14 in decimal.
Unset the \(n\)th bit
To unset a bit, we must &
with a 0
in the right place and &
with 1
everywhere else to keep everything intact. To obtain the binary string with a 0
in the nth position, we shift an 1
to the appropriate position and flip the entire value with ~
.
1 

1 2>>> unSetNthBit(1,10) 8
Explanation
This is what happens when we flip all the bits:
1 << 1 0 0 1 0 ~(1 << 1) 1 1 0 1 And, now we
&
them
10 1 0 1 0 ~(1 << 1) 1 1 0 1 10 & (1 << 1) 1 0 0 0 Clearly enough.
0b1000
is the same as 8 in decimal.
\(\)
Toggle that bit
Toggling a bit is similar to setting a bit, except that we ^
the bits instead of 
ing them. Remember that ^
ing a bit with 1
toggles it, whereas ^
ing with 0
keeps it as it is.
1 

1 2>>> toggleNthBit(3,10) 2
Explanation
10 1 0 1 0 1 << 3 1 0 0 0 10 ^ (1 << 3) 0 0 1 0
Extract the least significant bit
The least significant bit is given by
1leastSignificantBit = lambda x: x & (x)
Let's say that \(x\) is an integer with the binary representation \(s 1 0^n.\)
Now, the complement of \(x\) is \(s' 0 1^n.\)
Hence, \(x\) or the two's complement of \(x\) is \(s' 1 0^n \) (because by adding a 1, the 1's roll over and the 0 turns 1).
Now, we have the bitwiseand of \(x\) and \(x\) =
s100.... & s'100... = 100...
= \(1 0^n \) since the \(s\) and \(s'\) cancel out. \(_\square\)
1 2>>> leastSignificantBit(12) 4
Explanation
Let us assume that there are 8 bits allocated for each integer
12 0 0 0 0 1 1 0 0 12 1 1 1 1 0 1 0 0 12 & (12) 0 0 0 0 0 1 0 0
Count the number of set bits
This algorithm is attributed to computer scientist Brian Kernighan and famously known as Brian Kernighan's Algorithm
The function
countSetBits
defined as follows counts the number of set bits in an integer:
1 2 3 4 5 6def countSetBits(x): bits = 0 while x: bits += 1 x &= x1 return bits
Lemma Everytime we run through the line
x &= x1
, we turn off one bit.Proof The proof is similar to the proof in the last section.
Suppose \(x\) is an integer with the binary representation \(s 1 0^n.\)
Now, \(x  1\) is given by \(s 0 1^n\). This is because to subtract 1, we roll back the
0
s to1
s until we find a1
, in which case we stop.Now, we have the bitwiseand of \(x\) and \(x  1\) =
s100.... & s011...
= \(s \) since the right sides cancel out.Hence, we have lost one
1
\(_\square\)
Now, since we run through the loop (and increment the accumulator each time) until
n
completely runs out, we count the number of ones\(_\square\)
1 2>>> countBits(85) 4
Explanation
Notice that 85 is
0b1010101
.Here is what happens each time we run through the loop
x 1 0 1 0 1 0 1 x1 1 0 1 0 1 0 0 x & x1 1 0 1 0 1 0 0
x 1 0 1 0 1 0 0 x1 1 0 1 0 0 1 1 x & x1 1 0 1 0 0 0 0
x 1 0 1 0 0 0 0 x1 1 0 0 1 1 1 1 x & x1 1 0 0 0 0 0 0
x 1 0 0 0 0 0 0 x1 0 1 1 1 1 1 1 x & x1 0 0 0 0 0 0 0 The loop runs four times because there are 4 set bits.
Hamming Distance
The hamming distance between two integers is the number of bits which differ in them. To compute the hamming distance, we xor the two integers bitwise and count the number of bits set. This works because the xor yields 1
only when both bits are different.
1 

1 2>>> hamming(13, 11) 2
Explanation
13 1 1 0 0 1 11 1 0 0 1 1 13 ^ 11 0 1 0 1 0 Clearly
01010
has two set bits, which is the hamming distance between the two integers.
Other bit hacks
Here are some more interesting bit hacks. The reader could benefit by trying to explore how these hacks work.
Operation  Code  Example 
Turn off the rightmost 1bit  turnOff = lambda x: x & (x1)  01011000 \(\to\) 01010000 
Turn on the rightmost 0bit  turnOn = lambda x: x  (x+1)  10101011 \(\to\) 10101111 
Right propagate the rightmost 1bit  rightPropagate = lambda x: x  (x1)  01011000 \(\to\) 01011111 
Isolate the rightmost 0bit  isolateRightZero = lambda x: ~x & (x+1)  10101011 \(\to\) 100 