在所有8-bit的整数中,含有k个数字“1”的二进制数一共有C(8,k)个。给出其中的一个二进制数,你如何利用位运算快速找到下一个恰有k个“1”的数?例如,如果给你二进制数01011100,那么下一个(含4个“1”的)数就是01100011。在继续阅读下去之前,建议你仔细思考一下。你或许会想看看我很早以前写的一篇介绍位运算的文章。这是一道很好的题目,很多位运算技巧在这里都有体现。
在草稿纸上随便举几个例子,规律很容易看出来。由于“1”的个数是固定的,为了让这个二进制数更大,我们必须把第一个出现在“1”左边的“0”改成“1”;同时,为了让这个二进制数尽可能小,我们必须把它右边那些“1”重新排到最低位去。
更具体地说,下一个二进制数可以通过以下步骤得到:找到右起第一个单个的或连续的数字“1”,把它们全改成“0”,同时把它们左边的那个“0”改为“1”。此时,“1”的个数可能减少了,我们只需把还差的“1”摆在最右边就行了。举个例子,01011100的右起第一个“1”在第三位,把它和左边紧挨着的“1”一并变为“0”,并把再左边那个“0”变为“1”,于是我们得到01100000。我们还差两个“1”,把这两个“1”补在最低位得到01100011即可。现在我们的任务是,想出一个用位运算来实现这些步骤的办法。
我们已经熟知,用x & -x可以提取最右边的那个“1”。当意识到可以利用加法来消除连续的“1”时,我们很快得到了第一步操作的位运算实现:把x & -x加到x上,利用二进制加法的进位把“..01111..”变成“..10000..”。现在,我们需要计算出刚才的操作中一共“跳过”了多少个“1”,换句话说现在的x的右起第一个“1”和原来的x的右起第一个“1”差了多少位。关键就在这里!我们可以用除法来完成这一步,例如100000除以100就相当于把被除数右移2位,得到的结果即可以表示两个数中的“1”差了多少位。在最低位产生指定数量的“1”需要用到另一个技巧:减1操作可以把右边连续的“0”都变成“1”,即把…10000变成…01111。我们得到了该问题的第一个算法:
b = x & -x;
t = x + b;
c = t & -t;
m = (c/b >> 1) - 1;
r = t | m; //最终结果
我们对上述算法做一个简单的说明:
操作 | 样例 | 说明
——————+———-+—————————-
x | 01011100 | 原数
b = x & -x | 00000100 | 提取x的右起第一个“1”
t = x + b | 01100000 | 把x的右起第一个位于某个“1”左边的“0”变成“1”,并把它右边的那些“1”都变为“0”
c = t & -t | 00100000 | 提取t的右起第一个“1”
c / b | 00001000 | 右移c中的那个“1”,其结果中最低位连续的“0”的个数正好是c和b中的“1”相差的距离
m = (c/b >> 1) – 1| 00000011 | 在最低位产生数字“1”,其个数比上述的“距离”少1
r = t | m | 01100011 | 最终结果
除去赋值,我们一共用了9个运算符。有可能用更少的运算么?
回想x^(x-1)的作用:保留右起第一个“1”,同时把右起连续的“0”也都变为“1”;直观地说,“…10000”异或“…01111”得到“11111”。巧妙就巧妙在,我可以用c=t^(t-1)同时完成定位右起第一个“1”和产生足够多的数字“1”两个步骤。我们的新算法省下了一个运算,只需要8个运算符:
b = x & -x;
t = x + b;
c = t ^ (t-1);
m = (c >> 2) / b;
r = t | m; //最终结果
同样地,我们做一个简单的说明:
操作 | 样例 | 说明
——————+———-+—————————-
x | 01011100 | 原数
b = x & -x | 00000100 | 提取x的右起第一个“1”
t = x + b | 01100000 | 把x的右起第一个位于某个“1”左边的“0”变成“1”,并把它右边的那些“1”都变为“0”
c = t ^ (t-1) | 00111111 | 提取t的右起第一个“1”,同时把后面的“0”也全变为“1”
m = (c >> 2) / b | 00000011 | 把c右移两位,再右移b所表示的位数
r = t | m | 01100011 | 最终结果
现在,我们只用了8个运算符便完成了最初提到的一系列操作。这个数目还能再少吗?其实,这里面还有一个非常隐蔽的可改进之处:计算c时我们根本不需要用t来异或t-1,直接异或x就行了,它所产生的“1”的个数显然足够多。这样,我们又可以节省一个运算符了:
b = x & -x;
t = x + b;
c = t ^ x;
m = (c >> 2) / b;
r = t | m; //最终结果
操作 | 样例 | 说明
——————+———-+—————————-
x | 01011100 | 原数
b = x & -x | 00000100 | 提取x的右起第一个“1”
t = x + b | 01100000 | 把x的右起第一个位于某个“1”左边的“0”变成“1”,并把它右边的那些“1”都变为“0”
c = t ^ x | 00111100 | 提取t的右起第一个“1”,同时把后面足够多的“0”也全变为“1”
m = (c >> 2) / b | 00000011 | 把c右移两位,再右移b所表示的位数
r = t | m | 01100011 | 最终结果
这次,我们只用了7个运算就实现了题目的要求。还能继续优化吗?欢迎大家继续讨论!
来源:http://realtimecollisiondetection.net/blog/?p=78
沙发~~^_^
好强啊,以前看过构造组合的算法,不过是用bool数组实现
现在用位运算,那又降了一维吧
可以写个next_combination函数吧
http://forums.topcoder.com/?module=Thread&threadID=623246&start=0&mc=36
work hard ! tired
很强大的说
但是,用除法这种费时间的东西真的有用吗?
呵呵,看了你几篇关于位运算的文章,很有启发性啊!下面这道题我用递归解决的,牛牛看看能不能用位运算搞定,感觉好像可以,但没想出啥方法来。
题目:实现一个函数int func(unsigned int n),对一个正整数n,算得到1需要的最少操作次数:如果n为偶数,将其除以2;如果n为奇数,可以加1或减1;一直处理下去。
递归实现:
int function(unsigned int n)
{
if(n == 1) return 0;
if(n % 2 == 0) return (1 + function(n/2));
return (min(function(n+1), function(n-1)) + 1);
}
介绍一本书.机械工业出版社的就是专门讲类似的小技巧的.这篇Blog讲到的东东,里面也有讲到.
有人知道什么是open set么…
我不知道有没有办法解决地壳的问题…
写了一个程序输出了一下那个序列…
很没有规律…..
在OLES查了一下…有很多十分相类似的…却没有什么头绪的样子…#24
http://www.research.att.com/~njas/sequences/index.html?q=0%2C1%2C2%2C2%2C3%2C3%2C4%2C3%2C4%2C4%2C5%2C4%2C5%2C5%2C5%2C4&language=english
…顺便说一下..我觉得那本书里讲解一定没有这里好啦…
今天做了下…Ural 1057. Amount of degrees…
突然发现可以应用1下这个例子耶~
http://fayaa.com/tiku/view/47/
看到 b = x & -x 时突然有灵感了,在记事本中写了一下,发现和最后final的一样;曾经写过一个模拟组合函数C的小程序,假如当时就知道这种算法了,那该有多好!不过当时还小。。
很强大的说