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.