What is x - 1 wrt x

x - 1 is derived from x by flipping all bits to the right of (and including) the rightmost set bit (1) in x to 0s.

Examples

  • x = 4 (100 in binary), x - 1 = 3 (011 in binary).
  • x = 6 (110 in binary), x - 1 = 5 (101 in binary).

What is X & (x-1)?

x & (x - 1) results in a value with all bits from x remaining the same except for the rightmost set bit (1), which becomes 0.

Examples

  • x = 4 (100 in binary), x & (x - 1) = 0 (000 in binary).
  • x = 6 (110 in binary), x & (x - 1) = 4 (100 in binary).

Video explanation

Here is the video explaining this method in detail. Please check it out:

Notice (n & (n - 1)) == 0 for power of 2

Explain (n & (n-1)) == 0

Applications

Is Power of 2?

Powers of 2 have only one ‘1’ bit in set. Performing x & (x-1) for any number gives 0 only if x is a power of 2.

bool isPowerOfTwo(int x) {
  return (x!=0 && (x & (x - 1) == 0));
}

We have seen Explain (n & (n-1)) == 0, and this has application for Power of Two Problem.

Count Number of Bits Set in Number

The basic approach to evaluate the binary form of a number is to traverse on it and count the number of ones. But this approach takes log2N of time in every case.

Why log2N ? As to get a number in its binary form, we have to divide it by 2, until it gets 0, which will take log2N of time.

With bitwise operations, we can use an algorithm whose running time depends on the number of ones present in the binary form of the given number. This algorithm is much better, as it will reach to logN, only in its worst case.

More: Number of 1 Bits Problem.

int countBitsSet (int n) {
  while( n!=0 ) {
    n = n&(n-1);
    count++;
  }
  return count;
}

Why this algorithm works ? As explained in the previous algorithm, the relationship between the bits of x and x-1. So as in x-1, the rightmost 1 and bits right to it are flipped, then by performing x&(x-1), and storing it in x, will reduce x to a number containing number of ones(in its binary form) less than the previous state of x, thus increasing the value of count in each iteration.

Example: n = 23 = {10111}2 .

  1. Initially, count = 0.
  2. Now, n will change to n&(n-1). As n-1 = 22 = {10110}2 , then n&(n-1) will be {101112 & {10110}2, which will be {10110}2 which is equal to 22. Therefore n will change to 22 and count to 1.
  3. As n-1 = 21 = {10101}2 , then n&(n-1) will be {10110}2 & {10101}2, which will be {10100}2 which is equal to 20. Therefore n will change to 20 and count to 2.
  4. As n-1 = 19 = {10011}2 , then n&(n-1) will be {10100}2 & {10011}2, which will be {10000}2 which is equal to 16. Therefore n will change to 16 and count to 3.
  5. As n-1 = 15 = {01111}2 , then n&(n-1) will be {10000}2 & {01111}2, which will be {00000}2 which is equal to 0. Therefore n will change to 0 and count to 4.
  6. As n = 0, the the loop will terminate and gives the result as 4.

Complexity: O(K), where K is the number of ones present in the binary form of the given number.

Hamming Distance Between 2 Numbers

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. For eg.

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

Here this problem simply means - we just xor the 2 numbers, and count the bits which are set in the number.

public int hammingDistance(int x, int y) {
	int z = x ^ y;
	int count = 0;
	while (z!= 0){
		count++;
		z &= z-1;
	}
	return count;
}