github linkedin email
Jan 1, 0001
2 minutes read

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


comments powered by Disqus