Jan 1, 0001

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


Back to posts