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.

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\)

1

odd = lambda x: x & 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

We could easily extend the previous idea to check if the nth bit is set in an integer. The following returns a non-zero integer when the nth bit is set.

1

isNthBitSet = lambda n, x: x & (1 << n) #0-based indexing

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

To set a bit, we shift an 1 under the necessary place and apply bitwise OR.

1

setNthBit = lambda n, x: x | (1 << n)

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.

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

unSetNthBit = lambda n, x: x & ~(1 << n)

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.

\(\)

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

toggleNthBit = lambda n,x: x ^ (1 << n)

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

The least significant bit is given by

1	leastSignificantBit = 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 bitwise-and 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

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 6

def countSetBits(x): bits = 0 while x: bits += 1 x &= x-1 return bits

Lemma Everytime we run through the line x &= x-1, 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 0s to 1s until we find a 1, in which case we stop.

Now, we have the bitwise-and 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
x-1	1	0	1	0	1	0	0
x & x-1	1	0	1	0	1	0	0

x	1	0	1	0	1	0	0
x-1	1	0	1	0	0	1	1
x & x-1	1	0	1	0	0	0	0

x	1	0	1	0	0	0	0
x-1	1	0	0	1	1	1	1
x & x-1	1	0	0	0	0	0	0

x	1	0	0	0	0	0	0
x-1	0	1	1	1	1	1	1
x & x-1	0	0	0	0	0	0	0

The loop runs four times because there are 4 set bits.

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

hamming = lambda x,y: countSetBits(x ^ y)

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.

Here are some more interesting bit hacks. The reader could benefit by trying to explore how these hacks work.