简介

SWAR（SIMD Within A Register，寄存器内 SIMD）是一种分治算法，可以对一个寄存器中数据的不同分段进行并行计算。利用 SWAR 可以计算整数二进制中 1 的个数（Population Count）。
这个算法首先求出整数每 2 位的 1 的个数，然后相继将相邻的个数相加获得每 4 位、每 8 位（字节）的个数，最终求和获得整个 32 位整数二进制中 1 的个数。
算法所需的运算次数是固定的，时间复杂度为 ，没有额外使用内存空间。

算法

1. 计算每个 2 位组（duo）的 1 的个数

考虑一个只有 2 位的二进制数：
这个数的二进制中 1 的个数显然为各位数字加在一起：
转化成用 x_1x_0 推导：
真值表：



00 00 00
01 00 01
10 01 01
11 01 10
可以看出，这个计算不会发生从左侧的 2 位组借位的情况。
然而，在使用 SWAR 算法对 32 位整数进行处理时，右移操作会将奇数位送到右边 2 位组的偶数位。因此需要额外给偶数位置零才可以参与计算，求出全部 16 个 2 位组的 1 的个数： 
n -= (n >> 1) & 0x55555555; // C++14: 0b01010101010101010101010101010101

2. 将 2 位组的 1 的个数相加，得到每个 4 位组（nibble）的 1 的个数

考虑一个 4 位整数，由两个相邻的 2 位组构成，每个 2 位组存放了原整数相应位置 2 位组的 1 的个数。
利用相似的思路，将高 2 位置零可得低侧 2 位组的 1 的个数；将整数右移 2 位可得高侧 2 位组的 1 的个数，相加可得这个 4 位组的 1 的个数：

一个 4 位组的 1 的个数最大为 4（01002），最多占用 3 位，不会发生溢出。
在使用 SWAR 算法对 32 位整数进行处理时，右移操作会将低 2 位送到右边 4 位组的高 2 位，因此需要额外将高 2 位置零才可以参与计算： 
n = (n >> 2 & 0x33333333) + (n & 0x33333333); // C++14: 0b00110011001100110011001100110011

3. 将 4 位组的 1 的个数相加，得到每字节（byte）的 1 的个数

利用相似的思路，将一个字节中相邻两个 4 位组的 1 的个数相加，得到这个字节的 1 的个数。特殊的是，一个字节的 1 的个数最大为 8（10002），最多占用 4 位，因此不需要先将两个加数的高 4 位置零再相加，只需将整数和整数右移 4 位（将高 4 位的 1 的个数移到低 4 位）的结果直接相加，然后将和的高 4 位置零即可： 
n = (n >> 4) + n & 0x0F0F0F0F; // C++14: 0b00001111000011110000111100001111

4. 求 4 个字节的和

因为 32 位整数的 1 的个数最大为 32（1000002），最多占 6 位，不超过一个字节，此时可以将最后的步骤进行一定简化。下面介绍三种方法：

并行求和法

依照之前的思路，继续依次求出 16 位组和 32 位组的 1 的个数。由于上述原因，可以等求和完毕后再将最低 6 位以外其余部分置零： 
n += n >> 8;
n += n >> 16;
return n & 0x0000003F; // C++14: 0b00000000000000000000000000111111

算法的整个过程进行了 5 次加减法运算、5 次位移和 5 次按位与运算。

相乘累加法

我们可以利用乘法将 32 位整数的 4 个字节送上最高字节进行累加： 
         b3 b2 b1 b0
       × 01 01 01 01
       -------------
         b3 b2 b1 b0
      b3 b2 b1 b0
   b3 b2 b1 b0
b3 b2 b1 b0
--------------------
trunc'd |!!|
其中 b3、b2、b1、b0 分别为中间值的四个字节，trunc'd 指溢出的部分被截断，!! 是我们想要的和，位于积的 32 位整数的最高 8 位。
这个和一定不会大于 32，因此不用担心字节之间的溢出。将乘法运算的积直接右移 24 位，将求得的和送到最低字节，即可得到最终结果： 
return n * 0x01010101 >> 24;
算法的整个过程进行了 3 次加减法运算、4 次位移、4 次按位与运算和 1 次乘法运算。
这种方法在性能上并不差，因为 AMD 速龙（Athlon）起的 x86 处理器实现了快速整数乘法，大幅提高了这个方法的效率。

去 255 法

首先讨论这个方法的原理。
假设有一个 4 位的十进制数 。可知：

因此，如果 4 位之和小于 9，那么用这个数求对 9 的余数，即可得到 4 位之和。这个方法叫做“去九法”。
同理可以推广成“去 255 法”。我们有一个 32 位整数，每字节存放了一个最大为 8 的值，可以视作一个 4 位的 256 进制整数 。于是有：

因为 4 位之和不会大于 32，自然也不会大于等于 255。因此用这个数直接求对 255 的余数，即可得到 4 位之和，也就是我们想要的最终结果： 
return n % 255;
算法的整个过程进行了 3 次加减法运算、3 次位移、4 次按位与运算和 1 次除法运算。
直接编译成 CPU 的整数除法/求余指令性能不高，因为整数除法的效率非常低。一般情况下编译器会优化成定点倒数相乘，但是效率依然不如相乘累加法。

完整代码（C++） 

class Solution {
public:
    int NumberOf1(int n) {
        n -= (n >> 1) & 0x55555555;
        n = (n >> 2 & 0x33333333) + (n & 0x33333333);
        n = (n >> 4) + n & 0x0F0F0F0F;
        // 并行求和法
        n += n >> 8;
        n += n >> 16;
        return n & 0x0000003F;
    }
};