GO popcount

popcount : 計算整數二進位制中, bit 為 1 的 個數

介紹三種演算法：O(N) , O(log N), O(1)
O(N) : 一個個數

native solution

typedef unsigned __int64 uint64
int popcount_naive(uint64 x)
{
    int count = 0;
    for(; x; x>>1)
        ++count;
    return count;
}

less-native solution:

int pop_count_lnaive(uint64 x)
{
    int count = 0;
    for (; x; ++count)
        x&=x-1;
    return count;
}

GO 是用 O(log n) 和 O(1）方式:

先看最後用  math/bits package 的作法
 import "math/bits"

直接設計了函式 OnesCount() - https://golang.org/pkg/math/bits/#OnesCount

    func OnesCount(x uint) int

-- example:

package main

import (
"fmt"
"math/bits"
)

func main() {
fmt.Printf("OnesCount(%b) = %d\n", 14, bits.OnesCount(14))
}

底層做法: 

當為 32 bit 以內的, 查表法 - O(1)

// OnesCount8 returns the number of one bits ("population count") in x.
   119  func OnesCount8(x uint8) int {
   120   return int(pop8tab[x])
   121  }
   122  
   123  // OnesCount16 returns the number of one bits ("population count") in x.
   124  func OnesCount16(x uint16) int {
   125   return int(pop8tab[x>>8] + pop8tab[x&0xff])
   126  }
   127  
   128  // OnesCount32 returns the number of one bits ("population count") in x.
   129  func OnesCount32(x uint32) int {
   130   return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
   131  }

pop8tab[] 定義在 bits_tables.go

var pop8tab = [256]uint8{
	0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03, 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
	0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
	0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
	0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
	0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
	0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
	0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
	0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08,
	}

64 bit 使用 shift-and-add : O(log n)

// --- OnesCount ---
   103  
   104  const m0 = 0x5555555555555555 // 01010101 ...
   105  const m1 = 0x3333333333333333 // 00110011 ...
   106  const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
   107  const m3 = 0x00ff00ff00ff00ff // etc.
   108  const m4 = 0x0000ffff0000ffff
   109  

原理:

    e.g. x = x>>1 & m0 + x&m0
   m0 = 0x5555555555555555 // 01010101

先 2 bit 一組, 一個 bit 一個 bit 看, >>1 時把偶數bit AND進來, 兩個相加時, 若奇數 bit (e.g. bit0)
和 偶數 bit (e.g. bit1)都有時, 這組 2bit 值就會變成 2; 換言之, 這組 2bit 值就代表這兩個 bit 有 1 的個數

接著同此方式擴增到
  m1  4bit : m1 = 0x3333333333333333
  m2 8 bit : m2 = 0x0f0f0f0f0f0f0f0f


8bit 後就單純了, 把每 8bit 的值加起來, 而 64 bit 個數上限是 64, 只要 7個位元可以存下