# 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.