challenging bit manipulation procedure

2018-06-12 17:41:39

This question showed up on one of my teacher's old final exams. How does one even think logically about arriving at the answer?

I am familiar with the bit-manipulation operators and conversion between hex and binary.

int whatisthis(int x) {
  x = (0x55555555 & x) + (0x55555555 & (x >>> 1)); 
  x = (0x33333333 & x) + (0x33333333 & (x >>> 2));
  x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x >>> 4));
  x = (0x00ff00ff & x) + (0x00ff00ff & (x >>> 8));
  x = (0x0000ffff & x) + (0x0000ffff & (x >>> 16));
return x;
}

Didn't you forget some left shifts?

x = ((0x55555555 & x) <<< 1) + (0x55555555 & (x >>> 1));
x = ((0x33333333 & x) <<< 2) + (0x33333333 & (x >>> 2));
snip...

This would then be the reversal of bits from left to right.
You can see that bits are moved together rather than one by one and this lead to a cost in O(log2(nbit))
(you invert 2^5=32 bits in 5 statements)

It might help you to rewrite the constants in binary to understand better how it works.

If there are no left shifts, then I can't help you because the additions will generate carry and I can't see any obvious meaning...

EDIT : OK, interesting, so this is for counting the number of bits set to 1 (also known as population count or popcount)... Here is a squeak Smalltalk quick test on 16 bits

| f |
f := [:x |
    | y |
    y := (x bitAnd: 16r5555) + (x >> 1 bitAnd: 16r5555).
    y := (y bitAnd: 16r3333) + (y >> 2 bitAnd: 16r3333).
    y := (y bitAnd: 16r0F0F) + (y >> 4 bitAnd: 16r0F0F).
    y := (y bitAnd: 16r00FF) + (y >> 8 bitAnd: 16r00FF).
    y].
^(0 to: 16rFFFF) detect: [:i | i bitCount ~= (f value: i)] ifNone: [nil]

The first statement handle each bit pairs. If no bit is set in the pair then it produce 00, if a single bit is set, it produces 01, if two bits are set, it produces 10.

00 -> 0+0 -> 00 = 0, no bit set
01 -> 1+0 -> 01 = 1, 1 bit set
10 -> 0+1 -> 01 = 1, 1 bit set
11 -> 1+1 -> 10 = 2, 2 bits set

So it count the number of bits in each pair.

The second statement handles group of 4 adjacent bits:

0000 -> 00+00 -> 0000 0+0=0 bits set
0001 -> 01+00 -> 0001 1+0=1 bits set
0010 -> 10+00 -> 0010 2+0=2 bits set
0100 -> 00+01 -> 0001 0+1=1 bits set
0101 -> 01+01 -> 0010 1+1=2 bits set
0110 -> 10+01 -> 0011 2+1=3 bits set
1000 -> 00+10 -> 0010 0+2=2 bits set
1001 -> 01+10 -> 0011 1+2=3 bits set
1010 -> 10+10 -> 0100 2+2=4 bits set

So, while the first step did replace each pair of bits by the number of bits set in this pair, the second did add this count in each pair of pair...

Next will handle each group of 8 adjacent bits, and sum the number of bits sets in two groups of 4...

链接地址: http://www.djcxy.com/p/36396.html

上一篇: 用一次乘法提取位

下一篇: 挑战位操作过程