如何取得32位無符號數二進位表示是否含有奇數個1？
語言：經典C,不能使用條件語句，循環，分支，函數調用和宏調用，除法，模運算，乘法，比較運算，插入彙編語言。最多使用7次位運算/加減法。右移是算數右移（不過是求無符號數應該沒太大影響）
這是csapp家庭作業2.65,原題最多12次運算，我的方法也是網上最多的方法，11次位/加減運算。但是第三版p118旁註稱最少僅需7次，請問如何實現？
reg [31:0]din;
always @(posedge clk)
beg....不好意思走錯片場了做一個8bit的table,也就是256做成hash.然後把你要的計算的數學移為做與運算，查hash表，相加可得結果！
這個不是sse指令集裡面的么
__builtin_popcount如果要說沒有sse怎麼辦？那是生產沒有sse指令集的CPU廠商要考慮的事情。#include &
int main(int argc, char**argv)
{
unsigned int x = atoi(argv[1]);
//這裡未檢查參數的合法性
x = (x 0x55555555) + ((x&>&>1) 0x55555555); //0101010101010101...
x = (x 0x33333333) + ((x&>&>2) 0x33333333); //0011001100110011...
x = (x 0x0F0F0F0F) + ((x&>&>4) 0x0F0F0F0F); //0000111100001111...
x = (x 0x00FF00FF) + ((x&>&>8) 0x00FF00FF);//0000000011111111...
x = (x 0x0000FFFF) + ((x&>&>16) 0x0000FFFF);
printf ("num of 1: %d
", x);
}
我認為不存在只運算7次的解法（不允許打表的情況下）。
占坑，嘗試證明或推翻。
我知道的最優秀的演算法，進行了16次運算：
int bitCount_2(u32 x)
{
x-= ((x 0xAAAAAAAAu) &>&> 1);
x = ((x 0xCCCCCCCCu) &>&> 2) + (x 0x33333333u);
x = ((x &>&> 4) + x) 0x0F0F0F0Fu;
x = ((x &>&> 8) + x) 0x00FF00FFu;
x = ((x &>&> 16) + x) 0x0000FFFFu;
return x;
}
來自2014年集訓隊論文《回歸本源——位運算及其應用》
我很好奇題主的11次是如何實現的。
關於這個問題：
英文第三版問的是：是不是含有奇數個1？
中文第二版問的是：是不是含有偶數個1。
先放上所參考的網頁，大家可以直接去看這個： Question from bit twiddling site
本人找到的都是這種基於2分法的解答，其中奇數11次，偶數12次。
下面以奇數的解答為例：
方法(1)：採用典型的2分策略：
/* Return 1 when x contains an odd number of 1s; 0 otherwise Assume w=32 */
int odd_ones(unsigned int x)
{
unsigned int val= x ^ (x&>&>16);
val = (val&>&>8) ^ val;
val = (val&>&>4) ^ val;
val = (val&>&>2) ^ val;
val = (val&>&>1) ^ val;
val = val 0x1;
return val;
}
方法(2)：前半部分採用2分策略，後半部分的最後的4個位元組採用查表法，能夠節省2次操作：
找了一些代碼，我覺得下面的這個9次的算是容易理解，期待出現7次的解法(當然不包括查表～)：
/* Return 1 when x contains an odd number of 1s; 0 otherwise Assume w=32 */
int odd_ones(unsigned int x)
{
unsigned int val = 0;
val = x ^ (x&>&>16);
val = (val&>&>8) ^ val;
val = (val&>&>4) ^ val;
val = 0xF;
return (0x6996&>&>val) 1;
}
解釋一下， 最後一行的可以實現查表的效果：
(0x6996&>&>val) 1;
// 效果等同於 ch[val]，其中ch[16]={0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0};
// 可以省掉2個操作符(不考慮等號)，不用查表
//===================== 分割線 @_@！ ===========================
// 2017-04-01 更新 : 8次
int odd_ones(unsigned int x)
{
char* parts = (char*)(x);
char val = 0;
val = parts[0] ^ parts[1] ^ parts[2] ^ parts[3];
val = (val&>&>4) ^ val;
val = 0xF;
return (0x6996&>&>val) 0x01;
}
//===================== 分割線 @_@！ ===========================
// 2017-04-02 更新 : 7次，這個簡單跑了一下，應該算符合題意吧？
// -c99
int odd_ones(unsigned int x)
{
short* _16s = (short*)(x); // 32 -&> (16^16) -&>16
_16s[0] = _16s[0] ^ _16s[1];
char* _8s = (char*)_16s; // 16 -&> (8^8) -&>8
char val = 0;
val = _8s[0] ^ _8s[1];
val = (val&>&>4) ^ val; // 8-&> (4^4) -&>4
val = 0xF;
return (0x6996&>&>val) 0x01; // 相當於是查表
}
漢明重量
打表
```cpp
int cnt = 0;
while(x) {
x = (x-1);
cnt++;
}
```
推薦閱讀：