KingOfYellowAndBlack's blog

Are there any fast ways to reverse a range in a bitset?
By KingOfYellowAndBlack, history, 8 months ago, In English

Are there any non linear ways to reverse a bitset? For E.G the bitset 1001. Reverse from 1-3 and it would be 0011.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reverse an N-bit quantity in parallel in 5 * lg(N) operations:

unsigned int v; // 32-bit word to reverse bit order
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

Use this to flip all 32 integers in O(length*log w/w), then do a brute force flip with O(length/w).

→ Reply