[解決済み] このbitCountのコードがどのように動作するか、誰か説明してください。

質問

これはTAが教えてくれたコードなのですが、正しい答えを導き出すことができないので、それがどのように機能していたのか完全に忘れてしまいました、そして面接の採点は明日です。もし誰かが助けてくれるなら、お願いします。ありがとうございます。

* bitCount - returns count of number of 1's in word
*   Examples: bitCount(5) = 2, bitCount(7) = 3
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 40
*   Rating: 4
*/
int bitCount(int x) {
    int m4 = 0x1 | (0x1<<8) | (0x1<<16) | (0x1<<24);
    int m1 = 0xFF; 
    int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);
    int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1);
    return s1;
}

解決方法は？

ビット関連の演算は、ビット表現に変換すると何が起こるかわかりやすくなることが多い。

intが32ビットだとすると、m4 & m1をビットで表現すると次のようになります。

0000 0001 0000 0001 0000 0001 0000 0001 //m4, masking across the 4 bytes
0000 0000 0000 0000 0000 0000 1111 1111 //m1, masking only 1 byte, the Least Significant Byte (LSB)

mは マスク を意味し、4 & 1 は 4 バイトと 1 バイトずつ

そして、やっかいなのがs4です。順を追って調べていかないとわからないかもしれません。

まず、右ビットシフトとm4によるマスキングに注目してください。

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000w 0000 000w 0000 000w 0000 000w //x&m4

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 1
0pqr stuv wpqr stuv wpqr stuv wpqr stuv // x >> 1
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 7
0000 000p qrst uvwp qrst uvwp qrst uvwp // x >> 7
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4

そして2つ目は、上記の結果から得られた8つの要素の追加に注目してください。

0000 000w 0000 000w 0000 000w 0000 000w //x&m4
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4
---------------------------------------- +
//Resulting in s4

したがって、pからwはそれぞれ0か1しかなく、そのような要素は8個あるので、結果的に8ビットセグメントあたりで

p+q+r+s+t+u+v+w // each element is either 0 or 1

ここから、上記の8つの要素を足した結果は、0から8までの範囲になることがよくわかる。

つまり、8ビットセグメントあたり、0000 0000（10進数表現で0-すべて0の場合）～0000 1000（10進数表現で8-すべて1の場合）が得られることになります。

その結果、次のような形式のs4ができあがります。

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4

ここで abcd , エフエフ , ijkl および エムノップ は、1バイトごとにpからwを加算した結果です。

さて、ここで、あなたが 合計 は、4バイトにまたがるxのビット数です。

( 合計 ということなのでしょう。 s を意味する - sum)

0000 abcd //byte 1, left most, MSB
0000 efgh //byte 2, second from left
0000 ijkl //byte 3, second from right
0000 mnop //byte 4, rightmost, LSB

したがって、この4バイトの結果をs4で結合して 合計 で 一 バイト

(そして、私が思うに、これは s1 を意味します。 1バイトの和 )

でs1を取得します。

1. s4を0,8,16,24でシフトする
2. それぞれを0xFFでマスクする
3. そして、その結果を結合（足し算）します。

したがって、以下のような操作（ビットレベルでの）が発生します。

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 mnop

0000 0000 0000 abcd 0000 efgh 0000 ijkl // s4 >> 8
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 ijkl

.
.

0000 0000 0000 0000 0000 0000 0000 abcd // s4 >> 24
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 abcd

単純に4つの要素を以下のように追加していることがわかります。

0000 0000 0000 0000 0000 0000 0000 mnop //0 to 8
0000 0000 0000 0000 0000 0000 0000 ijkl //0 to 8
0000 0000 0000 0000 0000 0000 0000 efgh //0 to 8
0000 0000 0000 0000 0000 0000 0000 abcd //0 to 8
--------------------------------------- +
//Final result, s1

0から8の値を持つ4つの数字を単純に足し算したものです。したがって、その結果は0から32の値（0はすべてが0のとき、32はすべてが8のとき）でなければならず、これは変数xのビット1の数である。 ビットカウント .

これが関数の仕組みです。

最後に、これを知っていれば、m1を（0xFFではなく）0x0Fに変えても、結果は同じです。