Tutorial for bitwise operations

Bitwise techniques

Integers are represented in base 2 in computers. To know more about how they are represented and the different data-types supported please see this page.

Bitwise operators

The bitwise operators mentioned below with examples

& ( and ) : Do not confuse this with the && operator. This operator is used to AND two integers. The ANDing is done bitwise, that is the i-th bit of the left operand and i-th bit of the right operand are ANDed to give the i-th bit of the result.

For e.g.

13 & 14 = 12

   1101

& 1110

   ------

   1100

| ( or ) : Do not confuse this with the || operator. This operator is used to OR two integers. The XORing is done similar to that of the previous two operators.

For e.g.

13 | 14 = 15

  1101

| 1110

   ------

   1111

^ ( xor ) : This operator is used to XOR two integers. The XORing is done similar to that of the previous two operators.

For e.g.

13 ^ 14 = 3

   1101

^ 1110

   ------

   0011

~ (not): This unary operator returns the bitwise NOT of an integer. This is not to be confused with the logical not (!) operator.

For example, (!1) returns 0 (false), but (~1) returns 0xfffffffe; the logical value of both being true.

>> ( right-shift ) : The operator shifts the integer n, k-bits to the right and returns that if it's used as

n >> k. New ones are appended at the end.

Right-shifting is equivalent to dividing the number by 2^k.

<< ( left-shift ) : The operator shifts the integer n, k-bits to the right and returns that if it's used as

n << k. New zeros are appened at the end.

Left-shifting is equivalent to multiplying the number by 2^k. Thus the expression 1<<n represents 2ⁿ.

There is one more bit-shift operator for Java Programmers, that is the unsigned right-shift operator

>>> ( unsigned right-shift ) : While the signed right-shift operator ( >> ) shifts the bits to the right and the left most bits depends on sign extension, the unsigned right-shift operator ( >>> ) shifts zeros to the left most bits. Note that this operator is not in C/C++, as there are unsigned data types in C/C++ and not in Java.

How to check if the i-th bit is set in an integer

To check if a the i-th bit of a number n is set, we can see if ( n & 1 << i ) is non-zero. To be precise if the bit is set, then the result would be 2ⁱ. This is because in the number 2ⁱ there is only 1-bit and that is the i-th bit, if it's ANDing with n results in a non-zero number then the i-th bit is set in n.

How to check if an integer is a power of 2.

If x & ( x – 1) is zero then the number is a power of 2. Consider this as an exercise and try to understand why it's true.

Using integers to represent sets.

Let us consider an integer having k-bits we can use this integer to represent a subset of a set of k-elements . As we know each bit is either a 0 or a 1, thus we can use this to denote whether this element belongs to this given subset or not.

Now consider a set as shown

S = { a, b, c, d }

Consider the number 0101 in binary number system ( which is 5 in decimal number system ).

Now we can use this number to represent this subset

X = { b, d }

This is very trivial to understand however, it is a very important technique that must be known by all programmers.
We can use it to generate all the possible subsets of a set.

There are 2^k possible subsets of any given set with k-elements. What's more is that all these subsets can be described by numbers from 0 to 2^k-1 inclusive.

Thus the following pseudocode prints all the subsets of a given set ( this set is known as a power set )

start

    A[ 0..n-1 ] //set of n-elements

    for i := 0 to 2n

        print “subset no. i”
        for j := 0 to n
            if j-th bit is set in i
                print A[j]    
        end for
        print “\n”
    end for
end

Now that we have understood how to represent sets as integers. We can perform some operations on them

For e.g if set Ais represented by a and set B is represented by b

then the set a&b represents the intersection of the two sets, the set a|b represents the union of the two sets and the set a^b represents the symmetric difference of the two sets. You can think of more possible expressions such as a ^ ( a & b ) this means the set of elements belonging only to A and not to B.

Generating all subsets of a subset.

Consider a number 10110

The following numbers are subsets of this number

00000

00010

00100

00110

10000

10010

10100

10110

Now there's a nice and short way of generating them as shown below:

start

    N; //an integer

    X = N
    while true

        print X
        if( X == 0 )
            break;

        X = (X-1) & N;
    end while
end

Here the number X is a subset of number N.

Common bitwise tricks

x&(x-1) Returns number x with the lowest bit set off

x ^ ( x & (x-1 ) Returns the lowest bit of a number x

x & 1<<n Returns 1<<n if the n-th bit is set in x

x | 1<<n Returns the number x with the n-th bit set

x ^ 1<<n Toggles the state of the n-th bit in the number x

Only the most Significant bit is set

Given an integer x, return a number y with only the most significant bit in x set. It is same as the largest power of 2 that is no greater than x ( less than or equal to x )

Here we show, how to do this trick on a 32 bit integer. You can easily change it to work for others. Look what happens in following.

y = x;

y = y | ( y >>1 ) ;        y = y  | ( y >>2 );            y = y  | ( y >>4 );            y = y  | ( y >>8 );            y = y  |  ( y >>16 ) ;

You can see that the above right-shifting by powers of 2 and ORing at each step, sets all the bits starting from most significant bit set in x to the extreme right to 1. Now its simple to see,

y =  ( y + 1 ) >> 1;   has the required answer.

Surprisingly this is all you need to do for the problem http://www.codechef.com/problems/DCE05/ :) . See why does it work.

Problems to practice

http://www.spoj.pl/problems/PIZZALOC

HINT: Iterate over all possible subsets and check if they are feasible, Choose the best amongst all such feasible sets.

http://www.spoj.pl/problems/CERC07B

http://www.spoj.pl/problems/DFLOOR

It doesn't matter in what order you tap the tiles, so we decide to start tapping tiles from the first row. Then iterate over all possible ways of tapping the tiles on the first row, for each subsequent row you must only tap the tiles such that the previous row is fully lighted (or switched off in the other problem).

http://www.spoj.pl/problems/SUBSUMS

Divide the given set of numbers into two sets A and B. Generate all subsets of A and find the sum of each subset and store in an array. Sort this array. Similary generate subsets of B and for each subset find it's sum and use binary search on the sorted array of subsets of A to get the required answer ( Caution: Use 64-bit integers as answer can overflow a 32-bit integer )

Using integers to represent sets in a state

The following dynamic programming problems involve use of bitwise operators to represent states.

http://www.spoj.pl/problems/BABY

http://www.spoj.pl/problems/TRSTAGE

http://www.spoj.pl/problems/MMINPAID

http://www.spoj.pl/problems/M3TILE

http://www.spoj.pl/problems/HELPBOB

http://www.spoj.pl/problems/GNY07H

http://www.spoj.pl/problems/HIST2