Welcome to Rooeye's blog

De Bruijn序列求二进制串中最低位1的位置(末尾0的个数)

OJ rooeye 542℃ 0评论
求二进制串中最低位1的位置(末尾0的个数)方法很多,但是时间复杂度达到O(1)却很难,可以采用De Bruijn序列的方法。

概念解释:
1. De Bruijn序列:如果一个二进制串的长度为 2^n , 将其看成环形,首尾相连,从每一个字符开始进行n位截断,这样一共会产生 2^n个长度为n的二进制子串,如果这些子串全部互异,即这些二进制子串的值包含了从 0~2^n-1的所有值,那么我们称这样的二进制串为De Bruijn序列。

算法:
对于长度为 2^n 的二进制串,其末尾0的个数范围从 0~2^n-1(如果2^n位全为0则看作有0个0),刚好可以用n位的二进制全部表示。设 k = 长度为 2^n 的二进制De Bruijn序列串,那么 对于 k<<i(i=0,1,2,3…..2^n),随着i的不同,k << i的最高n位都不会相同,会得到从0~2^n-1的所有值,取高n位可以表示为 (k<<i)>>(2^n-n) ,设 t=(k<<i)>>(2^n-n) ,如果t=0,则表示有a0个0,如果t=1,则表示有a1个0…..,t的范围从0到 0~2^n-1,由此可以建立一个长度为 2^n 的数组,{a1,a2,…..,a2^n-1}。


eg:当n=5的时候,De Bruijn序列为 0x077CB531U,构建的表为 {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9}。
  1. int DeBruijn(int num)
  2. {
  3. int array[32] =
  4. {
  5. 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  6. 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  7. };
  8. int res = array[((unsigned int)(num & -num) * 0x077CB531U) >> 27];
  9. return res;
  10. }
代码解释:

1. 先要把给定数字num中除了最低位1以外的全部数字归0,(num & -num)意思是说:取num的从右边开始的0以及第一个1,比如:num = 101010100010101000000,num & -num = 1000000。(num & -num) * 0x077CB531U) >> 27 就是上面提到的 (k << i) >> (2^n-n).

完整版测试代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int DeBruijn(int num)
  4. {
  5. int array[32] =
  6. {
  7. 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  8. 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  9. };
  10. int res = array[((unsigned int)(num & -num) * 0x077CB531U) >> 27];
  11. return res;
  12. }
  13. int main()
  14. {
  15. printf("the res is %d\n",DeBruijn(123456));
  16. return 0;
  17. }

那么问题来了,De Bruijn序列是怎么构造出来的呢?这个问题可以转化为求一个有向图的欧拉回路问题。下列关于求De Bruijn序列的方法引用自:
http://www.cnblogs.com/shangdawei/p/3967505.html

如下图,构造一个包含 16 个顶点的图,顶点分别命名为 0000, 0001, 0010, …, 1111 。如果某个点的后 3 位,正好等于另一个点的前 3 位,就画一条从前者出发指向后者的箭头。也就是说,只要两个顶点上的数满足 abcd 和 bcde 的关系( a 、 b 、 c 、 d 、 e 可能代表相同的数字),就从 abcd 出发,连一条到 bcde 的路,这条路就记作 abcde 。注意,有些点之间是可以相互到达的(比如 1010 和 0101 ),有些点甚至有一条到达自己的路(比如 0000 )。


构造一个字符串使其包含所有可能的 5 位 01 子串,其实就相当于沿着箭头在上图中游走的过程。不妨假设字符串以 0000 开头。如果下一个数字是 1 ,那么 00001 这个子串就被包含了,同时最新的 4 位数就变成了 0001 ;但若下一个数字还是 0 ,那么 00000 就被包含了进来,最新的 4 个数仍是 0000 。

从图上看,这无非是一个从 0000 点出发走了哪条路的问题:你是选择了沿 00001 这条路走到了 0001 这个点,还是沿着 00000 这条路走回了 0000 这个点。同理,每添加一个数字,就相当于沿着某条路走到了一个新的点,路上所写的 5 位数就是刚被考虑到的 5 位数。我们的目的便是既无重复又无遗漏地遍历所有的路。显然图中的每个顶点入度和出度都是 2 ,因此这个图一定存在 Euler 回路,我们便能轻易构造出一个满足要求的 01 串了。这样的 01 串就叫做 De Bruijn 序列。

这样,就可以在O(1)时间内求出二进制串中最低位1的位置了.
参考:   http://www.cnblogs.com/shangdawei/p/3967505.html
来自为知笔记(Wiz)

转载请注明:寻梦人博客 » De Bruijn序列求二进制串中最低位1的位置(末尾0的个数)

喜欢 (2)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址