===== 真正强的东西来了！ =====
二进制中的1有奇数个还是偶数个
我们可以用下面的代码来计算一个32位整数的二进制中1的个数的奇偶性，当输入数据的二进制表示里有偶数个数字1时程序输出0，有奇数个则输出1。例如，1314520的二进制101000000111011011000中有9个1，则x=1314520时程序输出1。var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to 32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但这样的效率并不高，位运算的神奇之处还没有体现出来。
同样是判断二进制中1的个数的奇偶性，下面这段代码就强了。你能看出这个代码的原理吗？var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
为了说明上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如下：
00000000000101000000111011011000
XOR 0000000000010100000011101101100
—————————————
00000000000111100000100110110100
得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：
00000000000111100000100110110100
XOR 000000000001111000001001101101
—————————————
00000000000110011000101111011001
结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。
计算二进制中的1的个数
同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520（网友抓狂：能不能换一个数啊），那么最后x就变成了9，它表示1314520的二进制中有9个1。x := (x and $55555555) + ((x shr 1) and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211（我们班某MM的生日）来开刀。211的二进制为11010011。
+—+—+—+—+—+—+—+—+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <—原数
+—+—+—+—+—+—+—+—+
| 1 0 | 0 1 | 0 0 | 1 0 | <—第一次运算后
+——-+——-+——-+——-+
| 0 0 1 1 | 0 0 1 0 | <—第二次运算后
+—————+—————+
| 0 0 0 0 0 1 0 1 | <—第三次运算后，得数为5
+——————————-+
整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100….，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。
二分查找32位整数的前导0个数
这里用的C语言，我直接Copy的Hacker's Delight上的代码。这段代码写成C要好看些，写成Pascal的话会出现很多begin和end，搞得代码很难看。程序思想是二分查找，应该很简单，我就不细说了。int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n +16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位运算来取绝对值
这是一个非常有趣的问题。大家先自己想想吧，Ctrl+A显示答案。
答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值
x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。
高低位交换
这个题实际上是我出的，做为学校内部NOIp模拟赛的第一题。题目是这样：
给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。
当时几乎没有人想到用一句位操作来代替冗长的程序。使用位运算的话两句话就完了。var
n:dword;
begin
readln( n );
writeln( (n shr 16) or (n shl 16) );
end.
而事实上，Pascal有一个系统函数swap直接就可以用。
二进制逆序
下面的程序读入一个32位整数并输
灌……
水……
n = n + 2; x = x << 2;
这是C程序员写出的代码吗？
回复：还好只是copy的别人的，没丢人
不过我也不明白为什么书上要这么写
不管用什么语言 原来是学Pascal的本质很容易暴露哦
感觉传统的语言中,似乎只有COBOL比Pascal更像英文了.
某位大师说过,程序是数学写成的诗…
估计这也是,我一直用P的原因之一吧~
dd说的那个怎么了? C程序员是不会那么写… 但干嘛在这里说?
DD牛的意思应该是
n+=2;x<<=2;
这样写吧…
其实中间可以用逗号连接，这样连括号都省了…
为什么对于负数所有位取反,再加一就是它的绝对值?
回复：看（一）的最后面
这个我理解, 但这个的出处是哪里?
理解了, 原来是我习惯性地看东西跳过src带来的严重后果..
例如，1314520的二进制101000000111011011000中有9个1，则x=1314520时程序输出1
—————"效率"最高的写法(只需一行代码)—————
puts 1314520.to_s(2).count('1')%2
—————–当然这里的效率是指程序员(人)的效率———
Ruby-lang
[lol]
回复：我越来越想学ruby了
二进制逆序
下面的程序读入一个32位整数并输出它的二进制倒序后所表示的数。
输入： 1314520 （二进制为00000000000101000000111011011000）
输出： 460335104 （二进制为00011011011100000010100000000000）
——–ruby语言,一行代码解决问题:
puts sprintf("%032b","1314520").split(//).reverse.join.to_i(2)
午餐时候想到的,更简捷的写法:
puts sprintf("%032b",1314520).reverse.to_i(2)
哈哈!你太有个性了!211就211吧!还非要突出是你们班某MM的生日!哈哈
回复：突出那个MM在我心中的地位，随时忘不了提到她啊……
writeln('Matrix' , 42 XOR 105 , '原创，转贴请注明出处');
42 XOR 105 = 67 ?
[lol]
回复：嗯
只用位运算来取绝对值
这是一个非常有趣的问题。大家先自己想想吧，Ctrl+A显示答案。
答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值
x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。
___________________________________________________________________________
这个实现跟平台相关吧，有符号数左移，右移是未定义的行为吧。比如你这里的 x shr 31,如果x为负数的话，那么
x shr 31就为0xffffffff, not (x shr 31) + 1 等于0x00000000了。
为什么取绝对值时用
x:=x and not(1 shl 31);
当x为负数时会出201错误？（x是longint）
我怎么觉得二分查找32位整数的前导0个数的那个程序不对头也X=100时返回的是25, 我觉得应该是29呢?
二分查找32位整数的前导0个数的那个程序中20的前导0个数是27,而40是28, 40的前导0个数比20多??
回复：不会吧，我运行出来的不是这个结果
绝对值如果这样：x<>=1;
何如？
What’s that?????
您的程序的可读性实在是……
“求二进制中 1 的个数” 这样写如何？
var num, x: integer;
begin
readln(x);
num:=0;
while x0 do
begin
x:=x and (x-1);
num:=num+1;
end;
writeln(num);
end.
那么要知道二进制中最后一个1在第几位呢
有些系統的左移運算是循環左移,這個問題不可忽略!
答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值
只用位运算，可是有加号啊：-）
计算二进制中的1的个数还有一种叫做“HAKMEM算法”的方法，看上去似乎是某种诡异的三分法。
int Count(unsigned x){
unsigned n;
n = (x >> 1) & 033333333333;
x = x – n;
n = (n >> 1) & 033333333333;
x = x – n;
x = (x + (x >> 3)) & 030707070707;
x = x % 63;
return x;
}
计算二进制中的1的个数，wikipedia上的方法更诡异，可以做64位整数。
int popcount(unsigned long long x) {
typedef unsigned long long qword;
const qword m2 = ((qword)0x33333333<> 1) & (((qword)0x55555555<> 2) & m2);
x = (x + (x >> 4)) & (((qword)0x0f0f0f0f<<32)+0x0f0f0f0f);
return (x * (((qword)0x01010101<>56;
}
位运算 任意位取反 （把a 在b的1处取反 ）
a-(a and b) （反 a 中要反的 1）
a+((not(a xor b)) and b) (反 a 中要反的 0)
请教强人 是不是有点麻烦了
我是个菜鸟：您帮我看看那错了;
program finding;
var
i,m,n:longint;
procedure nlz(x:word);
var
n:integer;
begin
if x=0 then exit(32);
n:=1;
if ((x shr 16)=0) then begin n:=n+16; x:=x shl 16; end;
if ((x shr 24)=0) then begin n:=n+8; x:=x shl 8; end;
if ((x shr 28)=0) then begin n:=n+4; x:=x shl 4; end;
if ((x shr 30)=0) then begin n:=n+2; x:=x shl 2; end;
n:=n-(x shr 31);
exit(n);
end;
begin
assign(input,’input.txt’);
reset(input);
assign(output,’output.txt’);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
readln;
readln(m);
for i:=1 to n do
nlz(m);
end.
program finding;
var
i,m,n,k:longint;
a:array[1..1000000]of longint;
function nlz(x:word):integer;
var
n:integer;
begin
if x=0 then exit(32);
n:=1;
if ((x shr 16)=0) then begin n:=n+16; x:=x shl 16; end;
if ((x shr 24)=0) then begin n:=n+8; x:=x shl 8; end;
if ((x shr 28)=0) then begin n:=n+4; x:=x shl 4; end;
if ((x shr 30)=0) then begin n:=n+2; x:=x shl 2; end;
n:=n-(x shr 31);
exit(n);
end;
begin
assign(input,’input.txt’);
reset(input);
assign(output,’output.txt’);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
readln;
readln(m);
k:=nlz(m);
writeln(k);
close(input);
close(output);
end.
不好意思上次的那个发错了这个才是。。。
This Is My Life, RatedLife:
8.3Mind:
7.9Body:
9Spirit:
9.1Friends/Family:
6.3Love:
5.7Finance:
6.5Take the Rate My Life Quiz
怎么计算二进制中的0的个数？
回34楼
0的个数用32减去1的个数就得了呗……
Orz Martrix67 神牛………
明天就NOIP2009了
膜拜楼主！！！
第一个判1个数的奇偶性循环下就清爽了
for(y=1;y<=16;y<>y);
x xor (-(x shr 31))+(x shr 31) 也可以，好像是一样的
不错，不错
考虑可移植性是不是要用sizeof确定一下int的大小？
求绝对值只要把跟INT_MAX做一下AND操作不是就可以了吗？还是我考虑的太简单了？
为什么楼上= =||，我只是引用了而已啊，怎么会变成评论？
为什么楼上。。。我只是引用而已啊，怎么会变成评论？是WP的事情吗？好神奇
计算1个数15个运算符
今天无意查阅文档，发现X86指令集竟然直接提供了计算一个数字中1的个数的指令，不清楚Intel的CPU内部是如何实现的：POPCNT。
http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-us/fortran/lin/compiler_f/lref_for/source_files/rfpopcnt.htm
http://msdn.microsoft.com/en-us/library/bb385231.aspx
在交换高的16位与低的16位的时候，不知道有没有考虑到右移16位的时候会出现最高位的1填充的情况。在C语言中应该是写成:
x = (x<>16)&0x0000ffff)
不会pascal。另外回复一相#48楼的那个问题，那么指令很耗时间。
有没有办法只用位运算 不用-，取出pos的最高位
膜拜楼主！！！
08年intel在SSE里面加入了popcnt指令能单次运算得到整数中1的个数。在MSVC9(2008)以后的版本里面可以直接调用比如_mm_popcnt_u32()、_mm_popcnt_u64。这个目前是最快的方式。
位运算来取绝对值在java中不行哎
On Saturday evening, the promise D Chinese forest main field outside.Ex- the segment time’s ball team result keep on overcast.Influenced the seat of honor rate of ground.Before of compete, average seat of honor in ground in the city the rate return dissatisfied 20,000 people.The big slice of big slice of ground grandstand gets empty, the players also have no idea to compete in this kind of environment.
请问怎么看目录啊，找了五分钟都找不到目录，快抓狂了
可以搜索
哪里能看到完整的博客呢，找到的最后都是少了的