# bitwise problems

__1. Parity__

Parity is a proxy for number of set bits. The notion of parity was widely used in communication to ensure robust transmission of information. A parity check could catch error in transmission relating to a single bit of information.

$$ parity = \begin{cases} 0 \quad \text{if odd bits are set} \ 1 \quad \text{if event bits are set} \end{cases} $$ reset the last set bit for an integer

```
# reset the last set bit
# x = 1100 (12)
# x-1 = 1011 (11)
# x&(x-1) = 1000 (8)
x = x & (x-1)
```

We can build on this idea

```
result = 0 # start with even parity
# count the number of bits in x
while X!=0:
result ^= 1 # flips bits for even and odd parity
x = x & (x-1) # reset last set-bit
```

### Using a look up table will be faster on average:

If a word sie of 4 is used, 16 combinations are stored, i.e., an array of 16 is needed.

A integer of 32 bits will require **32/4=8** lookups.

__2. Swap bits__

Swap bits at two indices. Consider bits at index **i** and **j** in an integer.

```
x = 000010010010
i = 3
j = 7
# after swap x = 000000011010
```

It only makes sense to swap bits if they are not the same. If the bits are not the same it would mean using **xor **.

__3. Reverse bits__

Reverse the bits in an integer, a possible divide and conquer approach.

```
x = 1000
y = reverse(x)
# y = 0001
```

**use a look up table for reversing bits**

if I have a 32 bit integer, lets divide it into 8 segments of 4 bits each.

swap segment **i** with segment **(n-i)**, i.e., segment 0 will be swapped with segment 8, segment 1 with 7 and so on.

STOP swapping halfway to achieve the result of reversing bits.

The lookup table takes up space and a larger lookup table allows fewer segments and faster computation.

__4.Find closest Integer with same weight__

Weight of an integer is defined as the number of bits set in the integer. 1111 has a weight of 4, 0110 has a weight of 2.

```
# x&(x-1) reset the rightmost set bit
# (x&-x) truncate all bits left of rightmost set bit
fn_even = lambda x : (x&(x-1))^((x&-x)>>1)
fn_odd = lambda x : (x&(x-1))^((x&-x)<<1)
```