计算二进制整数中含有的1的个数的奇偶性


Table of Contents

问题描述

遇到过一个问题:判断一个数的二进制表示中含有的1的个数是偶数的还是奇数的。按照之前的做法,我会写一个循环,然后挨个判断这个数中每个位,记录下其中值为“1”的位的个数,最后给出结果。这种方法简单、直接,效率嘛,一般般,也没什么不好的。这两天在看《深入理解计算机系统》,其中有一道习题就是这个问题,而且还限制了不能用条件语句和循环语句来实现。这下,我就傻眼了。

解决方案

自己想了半天还是没有想到解决方案,不得以只能向Google求救,功夫不负有心人,总算让我找到解决方案了:

/* Return 1 when x contains an odd number of 1s; 0 otherwise.
   Assume w=32. */
int odd_ones(unsigned x)
{
  /* assume type unsigned take place 4 bytes */
  x = (x >> 16) ^ x;
  x = (x >> 8) ^ x;
  x = (x >> 4) ^ x;
  x = (x >> 2) ^ x;
  x = (x >> 1) ^ x;
  x = x & 1;

  return x;
}

实现很简单,对吧?我起初还不怎么信,但运行测试下来,确实是正确的。那么,这一堆移位操作,到底是怎么得到我们要的结论的呢?经过一番演算,总算让我找到一个证明方法了!

根据上面程序,执行过程为:

  1. 将x右移w/2位(w为unsigned类型占用的位数),然后将所得的值与x做异或运算,将结果保存替换x
  2. 将x右移w/4位,同样,将所得的值与x做异或运算,将结果保存替换x
  3. 重复运算,直到右移1位(即w/w位),将最后一次运算结果同样保存回x
  4. 取出最低有效位的值,当其为1时,代表原先的x中含有奇数个“1”,否则含有偶数个“1”

为了简化证明过程,我们假设unsigned类型占用8位,而非上面程序中设定的32位。 我们将x用向量的方式表示:\(\vec{x} = [x_{6}, x_{7}, …, x_{1}, x_{0}]\) 按照上面的步骤,8位的值x将进行4次移位与异或运算:

  1. 右移4位:\([0, 0, 0, 0, x_{7}, x_{6}, x_{5}, x_{4}] \oplus [x_{7}, x_{6}, x_{5}, x_{4}, x_{3}, x_{2}, x_{1}, x_{0}]\) \(= [x_{7}, x_{6}, x_{5}, x_{4}, x_{7} \oplus x_{3}, x_{6} \oplus x_{2}, x_{5} \oplus x_{1}, x_{4} \oplus x_{0}]\)
  2. 右移2位:\([0, 0, x_{7}, x_{6}, x_{5}, x_{4}, x_{7} \oplus x_{3}, x_{6} \oplus x_{2}]\) \(\oplus [x_{7}, x_{6}, x_{5}, x_{4}, x_{7} \oplus x_{3}, x_{6} \oplus x_{2}, x_{5} \oplus x_{1}, x_{4} \oplus x_{0}]\) \(= [x_{7}, x_{6}, x_{7} \oplus x_{5}, x_{6} \oplus x_{4}, x_{5} \oplus x_{7} \oplus x_{3}, x_{4} \oplus x_{6} \oplus x_{2}, x_{7} \oplus x_{3} \oplus x_{5} \oplus x_{1}, x_{6} \oplus x_{2} \oplus x_{4} \oplus x_{0}]\)
  3. 右移1位:\([0, x_{7}, x_{6}, x_{7} \oplus x_{5}, x_{6} \oplus x_{4}, x_{5} \oplus x_{7} \oplus x_{3}, x_{4} \oplus x_{6} \oplus x_{2}, x_{7} \oplus x_{3} \oplus x_{5} \oplus x_{1}]\) \(\oplus [x_{7}, x_{6}, x_{7} \oplus x_{5}, x_{6} \oplus x_{4}, x_{5} \oplus x_{7} \oplus x_{3}, x_{4} \oplus x_{6} \oplus x_{2}, x_{7} \oplus x_{3} \oplus x_{5} \oplus x_{1}, x_{6} \oplus x_{2} \oplus x_{4} \oplus x_{0}]\) \(= [x_{7}, x_{7} \oplus x_{6}, x_{6} \oplus x_{7} \oplus x_{5}, x_{7} \oplus x_{5} \oplus x_{6} \oplus x_{4}, x_{6} \oplus x_{4} \oplus x_{5} \oplus x_{7} \oplus x_{3}, x_{5} \oplus x_{7} \oplus x_{3} \oplus x_{4} \oplus x_{6} \oplus x_{2}, x_{4} \oplus x_{6} \oplus x_{2} \oplus x_{7} \oplus x_{3} \oplus x_{5} \oplus x_{1}, x_{7} \oplus x_{3} \oplus x_{5} \oplus x_{1} \oplus x_{6} \oplus x_{2} \oplus x_{4} \oplus x_{0}]\)

可以看出,最终结果为:\([x_{w-1}, x_{w-1} \oplus x_{w-2}, …, x_{w-1} \oplus x_{w-2} \oplus … \oplus x_{2} \oplus x_{1}, x_{w-1} \oplus x_{w-2} \oplus … \oplus x_{1} \oplus x_{0}]\) 如果对于上述结果还不太相信,OK,我们接下来看看当unsigned占用16位时的情况:

  1. 右移8位:\([0, 0, 0, 0, 0, 0, 0, 0, x_{15}, x_{14}, x_{13}, x_{12}, x_{11}, x_{10}, x_{9}, x_{8}] \oplus [x_{15}, x_{14}, x_{13}, x_{12}, x_{11}, x_{10}, x_{9}, x_{8}, x_{7}, x_{6}, x_{5}, x_{4}, x_{3}, x_{2}, x_{1}, x_{0}]\) \(= [x_{15}, x_{14}, x_{13}, x_{12}, x_{11}, x_{10}, x_{9}, x_{8}, x_{15} \oplus x_{7}, x_{14} \oplus x_{6}, x_{13} \oplus x_{5}, x_{12} \oplus x_{4}, x_{11} \oplus x_{3}, x_{10} \oplus x_{2}, x_{9} \oplus x_{1}, x_{8} \oplus x_{0}]\)
  2. 右移4位:\([0, 0, 0, 0, x_{15}, x_{14}, x_{13}, x_{12}, x_{11}, x_{10}, x_{9}, x_{8}, x_{15} \oplus x_{7}, x_{14} \oplus x_{6}, x_{13} \oplus x_{5}, x_{12} \oplus x_{4}]\) \(\oplus [x_{15}, x_{14}, x_{13}, x_{12}, x_{11}, x_{10}, x_{9}, x_{8}, x_{15} \oplus x_{7}, x_{14} \oplus x_{6}, x_{13} \oplus x_{5}, x_{12} \oplus x_{4}, x_{11} \oplus x_{3}, x_{10} \oplus x_{2}, x_{9} \oplus x_{1}, x_{8} \oplus x_{0}]\) \(= [x_{15}, x_{14}, x_{13}, x_{12}, x_{15} \oplus x_{11}, x_{14} \oplus x_{10}, x_{13} \oplus x_{9}, x_{12} \oplus x_{8}, x_{11} \oplus x_{15} \oplus x_{7}, x_{10} \oplus x_{14} \oplus x_{6}, x_{9} \oplus x_{13} \oplus x_{5}, x_{8} \oplus x_{12} \oplus x_{4}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}, x_{12} \oplus x_{4} \oplus x_{8} \oplus x_{0}]\)
  3. 右移2位:\([0, 0, x_{15}, x_{14}, x_{13}, x_{12}, x_{15} \oplus x_{11}, x_{14} \oplus x_{10}, x_{13} \oplus x_{9}, x_{12} \oplus x_{8}, x_{11} \oplus x_{15} \oplus x_{7}, x_{10} \oplus x_{14} \oplus x_{6}, x_{9} \oplus x_{13} \oplus x_{5}, x_{8} \oplus x_{12} \oplus x_{4}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}]\) \(\oplus [x_{15}, x_{14}, x_{13}, x_{12}, x_{15} \oplus x_{11}, x_{14} \oplus x_{10}, x_{13} \oplus x_{9}, x_{12} \oplus x_{8}, x_{11} \oplus x_{15} \oplus x_{7}, x_{10} \oplus x_{14} \oplus x_{6}, x_{9} \oplus x_{13} \oplus x_{5}, x_{8} \oplus x_{12} \oplus x_{4}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}, x_{12} \oplus x_{4} \oplus x_{8} \oplus x_{0}]\) \(= [x_{15}, x_{14}, x_{15} \oplus x_{13}, x_{14} \oplus x_{12}, x_{13} \oplus x_{15} \oplus x_{11}, x_{12} \oplus x_{14} \oplus x_{10}, x_{15} \oplus x_{11} \oplus x_{13} \oplus x_{9}, x_{14} \oplus x_{10} \oplus x_{12} \oplus x_{8}, x_{13} \oplus x_{9} \oplus x_{11} \oplus x_{15} \oplus x_{7}, x_{12} \oplus x_{8} \oplus x_{10} \oplus x_{14} \oplus x_{6}, x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{9} \oplus x_{13} \oplus x_{5}, x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{8} \oplus x_{12} \oplus x_{4}, x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}, x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2} \oplus x_{12} \oplus x_{4} \oplus x_{8} \oplus x_{0}]\)
  4. 右移1位:\([0, x_{15}, x_{14}, x_{15} \oplus x_{13}, x_{14} \oplus x_{12}, x_{13} \oplus x_{15} \oplus x_{11}, x_{12} \oplus x_{14} \oplus x_{10}, x_{15} \oplus x_{11} \oplus x_{13} \oplus x_{9}, x_{14} \oplus x_{10} \oplus x_{12} \oplus x_{8}, x_{13} \oplus x_{9} \oplus x_{11} \oplus x_{15} \oplus x_{7}, x_{12} \oplus x_{8} \oplus x_{10} \oplus x_{14} \oplus x_{6}, x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{9} \oplus x_{13} \oplus x_{5}, x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{8} \oplus x_{12} \oplus x_{4}, x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}]\) \(\oplus [x_{15}, x_{14}, x_{15} \oplus x_{13}, x_{14} \oplus x_{12}, x_{13} \oplus x_{15} \oplus x_{11}, x_{12} \oplus x_{14} \oplus x_{10}, x_{15} \oplus x_{11} \oplus x_{13} \oplus x_{9}, x_{14} \oplus x_{10} \oplus x_{12} \oplus x_{8}, x_{13} \oplus x_{9} \oplus x_{11} \oplus x_{15} \oplus x_{7}, x_{12} \oplus x_{8} \oplus x_{10} \oplus x_{14} \oplus x_{6}, x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{9} \oplus x_{13} \oplus x_{5}, x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{8} \oplus x_{12} \oplus x_{4}, x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}, x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2} \oplus x_{12} \oplus x_{4} \oplus x_{8} \oplus x_{0}]\) \(= [x_{15}, x_{15} \oplus x_{14}, x_{14} \oplus x_{15} \oplus x_{13}, x_{15} \oplus x_{13} \oplus x_{14} \oplus x_{12}, x_{14} \oplus x_{12} \oplus x_{13} \oplus x_{15} \oplus x_{11}, x_{13} \oplus x_{15} \oplus x_{11} \oplus x_{12} \oplus x_{14} \oplus x_{10}, us x_{13}, x_{14} \oplus x_{12}, x_{13} \oplus x_{15} \oplus x_{11}, x_{12} \oplus x_{14} \oplus x_{10} \oplus x_{15} \oplus x_{11} \oplus x_{13} \oplus x_{9}, x_{15} \oplus x_{11} \oplus x_{13} \oplus x_{9} \oplus x_{14} \oplus x_{10} \oplus x_{12} \oplus x_{8}, x_{14} \oplus x_{10} \oplus x_{12} \oplus x_{8} \oplus x_{13} \oplus x_{9} \oplus x_{11} \oplus x_{15} \oplus x_{7}, x_{13} \oplus x_{9} \oplus x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{12} \oplus x_{8} \oplus x_{10} \oplus x_{14} \oplus x_{6}, x_{12} \oplus x_{8} \oplus x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{9} \oplus x_{13} \oplus x_{5}, x_{11} \oplus x_{15} \oplus x_{7} \oplus x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{8} \oplus x_{12} \oplus x_{4}, x_{10} \oplus x_{14} \oplus x_{6} \oplus x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3}, x_{9} \oplus x_{13} \oplus x_{5} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2}, x_{8} \oplus x_{12} \oplus x_{4} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2} \oplus x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1}, x_{15} \oplus x_{7} \oplus x_{11} \oplus x_{3} \oplus x_{13} \oplus x_{5} \oplus x_{9} \oplus x_{1} \oplus x_{14} \oplus x_{6} \oplus x_{10} \oplus x_{2} \oplus x_{12} \oplus x_{4} \oplus x_{8} \oplus x_{0}]\)

从中可以看出一样的结论,因此通过最后一位的值可以判断出整个数中“1”是奇数还是偶数,而通过结果中第n位的值,则能够判断出原值中最高(w-n)位中,含有“1”的个数是奇数还是偶数。

Author: Rex Shen

Created: 2014-07-28 Mon 13:45

Emacs 24.3.1 (Org mode 8.2.7b)

Validate

Leave a comment

Your email address will not be published. Required fields are marked *