Bitwise operations

January 14, 2016

Bitwise operations can have a significant role in some algorithms. This article is intended to describe in the first part how bits work and how a signed number can be representated. Then we'll view the bitwise operators NOT, OR, AND, XOR and bit shifting <<. Least but not last, we'll explore some tips with these operators.

A bit, which stands for binary digit, is the basic unit of information, either 0 or 1. Usually, store data and execute instructions are not directly handled by bits but by bytes. One byte consists most commonly of eight bits.

As there is no other symbols than 0 and 1, signed numbers have to be represented with a method. The four best-known methods are sign-and-magnitude, ones' complement, two's complement and excess-K. The most common representation is two's complement. Let's see how it works. From now on, we'll use 8-bit numbers for simplicity, 16, 32 or 64 could be used in the same fashion.

The first idea that comes to mind is to use the most significant bit for the sign representation. 0000 0010 for 2 and 1000 0010 for -2. However, it comes up with two drawbacks. First, there are two representations for zero: 0000 0000 and 1000 0000. It's not a big deal.

Second, and more importantly, when adding two numbers, one positive and one negative, we can't simply use the common addition:

        3 +        -4 =        -1
0000 0011 + 1000 0100 = 1000 0111 (-7 instead of -1)

That's one reason why we ended up with two's complement. Negating a number is done by inverting all the bits (ones' complement) and then adding one to the result. Notice that we get fortunatly the same sequence of bits when applying the operation twice.

 4: 0000 0100
    1111 1011 <- inverting all the bits
    1111 1100 <- adding 1

-4: 1111 1100
    0000 0011 <- inverting all the bits
    0000 0100 <- adding 1

Other example:

0: 0000 0000
   1111 1111
   0000 0000

Another way to convert a number to its negative is to start at the least significant bit, copy all zeros until the first 1 is reached, copy that 1 and invert all the remainings bits.

Here are some examples:

Binary    | Two's complement
value     | interpretation
---------------------------
0000 0000 |     0
0000 0001 |     1
0111 1110 |   126
0111 1111 |   127
1000 0000 |  −128
1000 0001 |  −127
1000 0010 |  −126
1111 1110 |    −2
1111 1111 |    −1

Bitwise operators

NOT (¬)

The bitwise NOT is a unary operation giving the negative number. With the two'complement representation, NOT has to be computed with NOT x = -x - 1.

    x 0000 0010
   -x 1111 1101
---------------
 -x-1 1111 1100

AND (&)

The bitwise AND is performed by taking two numbers with the same bit length representation and compute the logical AND on each pair of corresponding bits, that is a multiplication.

    0010 0110
AND 0000 0011
-------------
  = 0000 0010

OR (|)

The bitwise OR is performed by taking two numbers with the same bit length representation and compute the logical OR on each pair of corresponding bits.

    0010 0110
OR  0000 0011
-------------
  = 0010 0111

XOR (^)

The bitwise XOR compute the logical exclusive OR on each pair. For every couple, the result is 1 if only the first bit is 1 or if only the second is 1.

    0010 0110
XOR 0000 0011
-------------
  = 0010 0101

Left shift (<<)

x<<y means x shifted y bits to the left. If you run out of space, the bits are just drop off.

0010 0110 << 2
--------------
1001 1000

0010 0110 << 4
--------------
0110 0000

Right shift (>>)

x>>y means x shifted y bits to the right. Similary, the bits are drop off if you run out of space.

0010 0110 >> 2
--------------
0000 1001

0010 0110 >> 4
--------------
0000 0010

Least significant 1 bit

In some cases, it's interesting to get the number equal to the least significant 1 bit. Due to the fact that negating a number is equivalent to keep the least significant 1 bit and invert all previous bits, we can find that x&-x gives the correct number.

   x 0010 0110
  -x 1101 1010
x&-x 0000 0010

Transform the least significant 1 bit to 0

By observing that x-1 transforms the least significant 1 bit into 0 and keep all previous bits unspoiled, the wanted number can be calculated with x&x-1.

    x 0010 0110
  x-1 0010 0101
x&x-1 0010 0100

Note that it's working with x=0.

    x 0000 0000
  x-1 1111 1111
x&x-1 0000 0000

This gives the background to understand the next incoming post: fenwick tree.

References:

  1. Bitwise operation - wikipedia
  2. Bit - wikipedia
  3. Signed number representation - wikipedia
  4. Bit (binary digit) - whatis.techtarget.com
  5. Bit twiddling hacks - graphics.stanford.edu