Bit Manipulation

Here are some resources to learn about bit manipulation:

Chapter 5 of Cracking the Coding Interview
Bit Manipulation Tutorial (many examples)
What is two's complement? (this is how integers are represented in the computer)

Optional

What USEFUL bitwise operator code tricks should a developer know about?

Bit Manipulation Reference

The basic bit manipulation operations are ~ (NOT),& (AND), | (OR) and ^ (XOR). For each bit in a and b, the resulting bit is the following:

a	b	a & b	a \| b	a ^ b	~a
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	0
1	1	1	1	0	0

You can use hex notation to create bit masks:

int mask = 0xFFFFFFFF; // (bit mask of all ones)
int mask = 0xAE;       // 1010 1110

For debugging purposes, look up how to print integers as binary strings in your favourite language.

Examples

Try to do each example by yourself first.

x & (x - 1)

What does x & (x - 1) do? Why would we want to do this? x is an integer.

Solution

Note: I'm arranging the bit string most to least significant from left to right. So when I say left, I mean more significant.

To get an answer that is more insightful than "it gives you the AND of x and x - 1" (that's not very useful, is it?), we have to look at what this is doing to the bits of x. One approach is to begin by considering two cases:

The least significant bit in x is 1.
The least significant bit in x is 0.

Case 1 is easy to imagine. If the least significant bit is 1 in x then x - 1 is the same as x except the least significant bit is now 0. Recall that AND will give 1 when both bits are 1 and 0 otherwise. Since all the other bits are the same the AND of x and x - 1 gives you back x - 1. In other words, it clears the last bit of x.

Case 2 is a bit more tricky. If the least significant bit is 0 then subtracting 1 requires borrowing from a more significant bit. If the bit to the immediate left is 1, then we "borrow" a 1 and then do our subtraction. If the bit to the immediate left is 0 then we keep going left until we find a 1 from which we can borrow and carry it over. This flips all of the 0's to its right to 1.

(If you're not familiar with subtracting binary numbers, take a look at this video.)

In other words, we go left until we find a 1. It gets set to 0, and all the 0's to its right become 1. Here is an example, suppose you have the bit string 101000:

  101000
-      1

After borrowing...

  100112
-      1
--------
  100111

What happens when we AND these numbers together? When we subtract 1, we essentially flipped the bits of everything to the right of the least significant 1 bit (including that 1 bit). When we AND two flipped bit strings, we get 0. So everything to the right of the least significant 1 bit becomes 0. Everything to the left of the least significant 1 remains the same. In other words, we're clearing the least significant 1 bit.

In case 1, we were also clearing the least significant 1 bit! So the answer is that x & (x - 1) clears the least significant 1 bit.

Follow up

What does x & (x - 1) == 0 do?

What does this code do?

  void mystery (int x) {
      int ret = 0;
      while (x != 0) {
          x = x & (x - 1);
          ret++;
      }
      return ret;
  }

Reverse Bits

(From LeetCode)

Reverse bits of a given 32 bit unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Solution

public int reverseBits(int n) {
    int result = 0;
    // For every bit:
    for (int i = 0; i < 32; i++) {
        // Shift our result left to make room.
        result <<= 1;
        // Transfer n's bit at position 1 to result.
        result |= (n & 1);
        // Shift n right.
        n >>= 1;
    }
    return result;
}

For every bit in n, we transfer n's rightmost bit to m's rightmost bit. Then we shift n right so that n's next bit to the left is in the rightmost position. If you are unfamiliar with bit operations, check out the resources given at the top.

Can you think of a way to reverse the bits using XOR? (XOR solution)

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it using constant additional memory?

Hint

You can easily solve this problem by using a hash set. For each number, you put it in a hash set. If a number already exists in the hash set, remove it. Whichever number remains in the hash set at the end is the non-duplicate. If only allowed constant additional memory then this solution is not viable and we have to think of something else.

Suppose we write out the bits of all the numbers and aligned their bits together. We would see that in each bit position, two numbers that are the same will contribute two 0's or two 1's (depending on which bit they have in that position). The unique number would only contribute one 0 or one 1 bit. Which bit operation can you use to take advantage of this?

Solution

If we XOR two bits that are the same, we get 0 so if we XOR two numbers that are the same we end up with all 0s. What happens when we XOR a number with 0? We get the same number back because:

a	b	a XOR b
0	0	0
1	0	1

If we XOR all the elements of the array together, the duplicates will cancel out (giving us 0). The result will be the unique element XORed with all 0s, giving us that unique element. This works because the order of XOR does not matter.

public int singleNumber(final List<Integer> list) {
    int n = 0;
    for (int i = 0; i < list.size(); i++) {
        n = n ^ list.get(i);
    }
    return n;
}

Counting Bits

(From LeetCode)

Given a non negative integer number num. For every numbers in the range calculate the number of 1's in their binary representation and return them as an array.

Example: For num = 5 you should return [0,1,1,2,1,2].

Can you do it in time?

Solution 1

The most obvious solution which runs in O((# bits in n) * n) time is to count the number of bits in each number from 1 ... n.

public int[] countBits(int num) {
  int[] b = new int[num + 1];
  for (int i = 1; i <= num; i++) {
    int count = 0, j = i;
    while (j != 0) {
      if ((j & 1) == 1)
        count++;
      j /= 2;
    }
    b[i] = count;
  }
  return b;
}

Can you think of a solution that runs more efficiently?

Solution 2

Let b[i] contain the number of bits for integer i. We can solve this problem inductively: assume that we have the number of bits for every in the range (b[0 ... i - 1]). How can we find b[i]?

If i is odd then it has one more 1 bit than i - 1 therefore b[i] = b[i - 1] + 1.
If i is even then it has the same number of bits as i >> 1 therefore b[i] = b[i >> 1].

The base case is i = 0 in which case b[0] = 0.

This gives us a more efficient solution:

public int[] countBits(int num) {
  // By default arrays are zero filled in Java so b[0] = 0
  int[] b = new int[num + 1];
  for (int i = 1; i <= num; i++) {
    if (i % 2 == 1)
      b[i] = b[i - 1] + 1;
    else
      b[i] = b[i >> 1];
  }
  return b;
}

Bit Manipulation

Bit Manipulation

Examples

x & (x - 1)

Reverse Bits

Single Number

Counting Bits

results matching ""

No results matching ""