Category Archives: Bit magic

Check if array can be divided into two parts with same XOR

Given an array of numbers, how do we check if it can be divided into two parts such that XOR values of both are same.

For example consider an array A = [1, 2, 3], it can be divided into [1, 2], and [3] because 0001 ^ 0010 = 0011

Similarly, [8, 3, 12, 7], can be divided into [8,7] and [3, 12] as 1000 ^ 0111 = 0011 ^ 1100 = 1111

This is a tricky question, where you need not actually try to divide the numbers into two sets. If any two parts of the array have the same XOR value, the XOR of all the elements will be Zero.

So we just need to check if the XOR value of all the elements is zero or not.

Maximum Xor of two bit patterns

Given two numbers A, B, What is the maximum value of A' XOR B', where A', B' are obtained by permuting the binary representations of A, B respectively.

For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A' = 1100, B' = 0010, then we get the A' ^ B' = 1110 = 13. So 13 is the answer. For no other values of A’, B’, the XOR will be maximum.

Let us look at another example A = 3, B = 7, again represented using 4 bits. A' = 0011, B' = 1101 and A' ^ B' = 0011 ^ 1101 = 1110 = 14. So 14 is the answer.

This problem was originally appeared on Codechef. The problem has 3 inputs N (number of bits), A, B. How many 1s are possible in the result number?

Since 1^0 = 1 and 0^1 = 1, to get a 1 in the final result, We should have a

  • 1 bit in A, and 0 bit in B or
  • 0 bit in A, and 1 bit in B

So the total number 1s possible in the result is Minimum( 1s in A, 0s in B) + Minimum( 0s in A, 1s in B). The remaining bits are Zeros.

How should we arrange these bits to get the maximum value? All 1s should be pushed to left (Most significant bits). So the result will be of the form 1111…00

Here is the Java code which implements the above approach.

Clearing the right most set bit in a binary number

Given an integer, write a program to clear the right most set bit in it’s binary representation.
For example, consider a number 54. It is represented in binary as  
1 1 0 1 1 0
The right most set bit is marked in bold. We need to convert this to 
1 1 0 1 0 0
Let us look at the approach step by step.

If you negate the number to -54, it is represented in computer’s memory in 2’s compliment.

0 0 1 0 1 0

Let us perform a bit-wise AND operation between these two.

1 1 0 1 1 0
0 0 1 0 1 0
————&
0 0 0 0 1 0

Subtract this from the original number to get the result. So x – ( x & -x) gives the required answer.

Here is the simple program to test the above.

Finding two numbers occuring once

Given an array containing all elements twice except two numbers. Write a program to find those two numbers.
For example let us consider the following array
{2, 3, 2, 1, 4, 1, 4, 5} 
The answer is {3,5} because they appear only once and all remaining elements appear twice.
This question is somewhat similar to earlier post. This gives us a hint to use XOR operation to solve this problem. Let us see how we can utilize XOR operation.
We first find the XOR of all the elements in the array. This gives a bit pattern which is an XOR of required two values because all other elements occurs twice they get zeroed out.

For the above example the xor value is 0110 = 0011 ^ 0101

Let the two unique numbers are x, y. The next problem is how to find x,y from this xor value. Let us denote ith bit is the first set bit in the xor result. We divide all the numbers in the array into two parts. One part containing all the numbers with bit i = 1, and the other part containing all the numbers with bit i = 0;

This partition segregates the numbers such that all the pairs with ith bit 1 goes to one partition and all pairs with ith bit 0. But x and y fall into two different buckets their bit patterns will be different.

Now finding the XOR value of these partitions separately gives us the required result.

In the above example. The XOR value has 1st bit as 1.
{2,2,3} forms one partition and {1,1,4,4,5} forms another partition.

Parition-1    Partion-2
0010          0001
0011          0100
0010          0001
                 0100
                 0101
———————
 0011(3)     0101(5)

 So 3,5 are the answers

Here is the Java code to do this.


Number of bits to change from one number to other

Given two numbers, calculate the number of bits required to change from one number to the other.
For example 12 in binary can be represented as 1100. 15 is represented as 1111. We need to change two bits to convert one number from the other as the last two bits are different.
We can find out the difference bits as follows. We first find out the XOR of two numbers. This gives us a bit pattern in which there is a set bit, if two bits differ. Then we can calculate the number of set bits in the XOR which gives the required answer.
Here is C++ code for this.

Finding the unique number in an array

Given an array of numbers which contains all the numbers in pairs expect one element. We have to find that unique element.

For example in the array [7,3,8,1,3,4,7,1,8] 4 is the unique element and all the remaining elements occur in pairs.

This is actually a specific case of more generic problem discussed in the my previous post. 

http://comproguide.blogspot.in/2013/06/finding-element-occurring-odd-number-of.html

please refer to the above post for complete solution.

Printing the number in binary format

How do we write a program to print the binary representation of an integer?

For the sake of simplicity, let us assume that the integer takes 32 bits. The integer 367 is represented in binary as follows.

0000 0000 0000 0000 0000 0001 0110 1111

Iterative Method:

In this method we extract the bit at each of the 32 positions from left to right. The bit at ith position can be found by performing bit-wise & operation between the following numbers
2i & num

In the following  Java Program, 2i is calculated by 1<<i. This is efficient way of calculating 2 raised to the power of i. This method prints all the leading 0s also.

public static void printBinary(int num)
{
int i = 31;

while( i >= 0)
{
int mask = 1 << i;
int bit = (num & mask) == 0 ? 0: 1;
System.out.print(bit);
i--;
}
System.out.println();
}


Recursive Method:

In this function as long as num > 0, we recursively call the function by halving the number. When the number reaches 0, the stack unwinding happens. We print the remainder of num when divided by 2 (num%2). This method trims all the leading 0s if present but this works for only for non-negative integers.

public static void printBinaryRecursive(int num)
{
if( num > 0)
{
printBinaryRecursive( num/2 );
System.out.print( num%2 );
}
}


Checking if a number is power of 2

Given an integer how do we check if it is a power of 2?

For example 1, 2, 4, 8, 16, 32, 64, 128, 256,… are integral powers of 2.

There are several methods to check if a number is a power of 2.

Method#1: Using repeated division

If you repeatedly divide the number by 2 (without any remainder), You will finally get a 1 if it is a power of two.

For example if the number is 64

64/2 = 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1

If the number is 22

22/2 = 11/2 = 5 (we stop here as there is a non-zero remainder)

public static boolean isPowerOfTwo(int num)
{
if( num <= 0 )
return false;

while( num > 1)
{
if( num %2 != 0)
return false;
num = num/2;
}
return true;
}


Method#2: Counting the set bits
If you consider the binary representation of the numbers, The powers of 2 always contain just one set (1) bit.

For example

1 = 0000 0001
2 = 0000 0010
4 = 0000 0100
8 = 0000 1000
16 = 0001 0000

So by counting the number of set bits and checking if it is 1, we can conclude that it is a power of 2

Please check my previous post for counting the set bits in a number.

Method#3: Efficient and clever
This method is also based on an observation of binary representation of numbers. 
We all know the Bit-wise and (&) operation . If it is represented by the following table

A   B    A&B
————–
1   1      1
1   0      0
0   1      0
0   0      0

If the number n is a power of 2, then the bit-wise and operation between n and (n-1) is always 0.

For N = 64                 0100 0000 = 64
                           0011 1111 = 63
                          ————- &
                           0000 0000
 

 public static boolean isPowerOfTwo(int num)
{
if( num <= 0 )
return false;

return (num & (num-1)) == 0? true: false;
}

Counting the set bits in a number

Given an integer, how do we count the number of set (1) bits?

For example the number 37 has 3 set bits in it’s binary representation (0010 0101)

Method#1: Simple

In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1 we increment the count. In the next iteration we right shift the number by one bit and repeat the same operation until the number becomes 0.

public static int getSetBitCount(int num)
{
int count = 0;

while( num > 0)
{
if( (num & 1) == 1)
count++;
num = num >> 1;
}
return count;
}

This method has a drawback that even if there less number of set bits, we have to go through all the bits to count the set bits. 
For example If the given number is 129 ( 1000 0001).  It unnecessarily goes though all the 0s between the first and last 1s.
Next method overcomes this drawback.

Method#2: Kernighan & Ritchie Method

This method is a slight improvement of the previous method where it skips the zeroes wherever they appear. 

This method is based on the observation that performing a bit-wise & operation between num and (num-1) clears the right most set bit.

For example if num = 39
0010 0111
0010 0110
———-&
0010 0110 

The number of iterations in this algorithm is based on the number of set bits. If number is 129 we can find the set bits in just two iterations.

1000 0001 = 129
1000 0000 = 128
———-&
1000 0000 = 128
0111 1111 = 127
————-&
0000 0000
 

public static int getSetBitCount(int num)
{
int count = 0;

while( num > 0)
{
num = num & (num-1);
count++;
}
return count;
}