位运算之BitMask

之前出过一道题 http://xujcoj.org/Home/Problems/status/pro_id/1034 目的是为了让做这道题的同学掌握利用位运算实现20以内的暴力搜索,因为2的20次方大概在1e6左右,刚好符合一般题目的复杂度。

后来在Codeforces上做了这样一道题 http://codeforces.com/contest/1288/problem/D,在二分的过程中,每次都需要利用位运算进行一次暴力搜索,但不同于上一道题的是,这是一个带<约束条件>的搜索。如何去理解这个约束,例如:有三个数字,如果都可以选的话,我们就从状态000遍历到状态111,实际上就是让一个数字从0跑到7就可以了。但是如果规定第二个数字不能选怎么办,也就是我们只需要考虑000,001,100,101这四种状态,不嫌麻烦的话的确可以把每一位有效数字的位置都存起来,用它们去做一个全暴力搜索,好比这个例子,我们只需要把0和2存下来(数字的下标),然后跑一个从状态00到状态11的循环,每一位对应到刚才存下来的数字上就好了,但是在这里,我分享一种更好的方法,废话不多说,先上代码。

int n = 13;
for (int x = n; x; x = (x - 1) & n)
{
	cout << x << endl;
}

这段代码将输出以下数字:13 12 9 8 5 4 1。

仔细观察后不难发现,13的二进制表示是1101, 12是1100, 9是1001, 8是1000, 5是0101, 4是0100, 1是0001,这个循环把13各个位置上的1出现与否的情况全部跑了一遍(除了0)!至于为什么,我就不知道了。(总之很神奇)

这里给一道例题供大家掌握这个算法:http://xujcoj.org/Home/Problems/status/pro_id/1309

至于如何取某个数字各个位置上的数(转二进制),请参考 这篇文章

评论已关闭

  • 太棒了,学到许多!