一個關于用戶標簽的需求
為了幫助公司精準定位用戶群體，咱們需要開發一個用戶畫像系統，實現用戶信息的標簽化。
用戶標簽包括用戶的社會屬性、生活習慣、消費行為等信息，例如下面這個樣子。
通過用戶標簽，我們可以對多樣的用戶群體進行統計。例如統計用戶的男女比例、統計喜歡旅游的用戶數量等。
為了滿足用戶標簽的統計需求，小灰利用關系數據庫設計了如下的表結構，每一個維度的標簽對應著數據庫表中的一列：
要想統計所有“90后”的程序員，該怎么做呢？
用一條求交集的SQL語句即可。
看起來很簡單嘛，嘿嘿……
事情沒那么簡單，現在標簽越來越多，例如，用戶去過的城市、消費水平、愛吃的東西、喜歡的音樂……都快有上千個標簽了，這要給數據庫表增加多少列啊！
篩選的標簽條件過多的時候，拼出來的SQL語句像面條一樣長……
不僅如此，當對多個用戶群體求并集時，需要用distinct來去掉重復數據，性能實在太差了……
用BITMAP算法解決問題
你聽說過Bitmap算法嗎？在中文里叫作位圖算法。
這里所說的位圖并不是像素圖片的位圖，而是內存中連續的二進制位（bit）所組成的數據結構，該算法主要用于對大量整數做去重和查詢操作。
舉一個例子，假設給出一塊長度為10bit的內存空間，也就是Bitmap，想要依次插入整數4、2、1、3，需要怎么做呢？
很簡單，具體做法如下。
第1步，給出一塊長度為10的Bitmap，其中的每一個bit位分別對應著從0到9的整型數。此時，Bitmap的所有位都是0（用紫色表示）。
第2步，把整型數4存入Bitmap，對應存儲的位置就是下標為4的位置，將此bit設置為1（用黃色表示）。
第3步，把整型數2存入Bitmap，對應存儲的位置就是下標為2的位置，將此bit設置為1。
第4步，把整型數1存入Bitmap，對應存儲的位置就是下標為1的位置，將此bit設置為1。
第5步，把整型數3存入Bitmap，對應存儲的位置就是下標為3的位置，將此bit設置為1。
如果問此時Bitmap里存儲了哪些元素，顯然是4、3、2、1，一目了然。
Bitmap不僅方便查詢，還可以去掉重復的整數。
你仔細想一想，你所做的用戶標簽能不能用Bitmap的形式進行存儲呢？
我的每一條用戶數據都對應著成百上千個標簽，怎么也無法轉換成Bitmap的形式啊？
別急，我們不妨轉換一下思路，為什么一定要讓一個用戶對應多個標簽，而不是一個標簽對應多個用戶呢？
信息不一定非要以用戶為中心存儲，也能夠以標簽為中心來存儲，讓每一個標簽存儲包含此標簽的所有用戶ID，就像倒排索引一樣！
第1步，建立用戶名和用戶ID的映射。
第2步，讓每一個標簽存儲包含此標簽的所有用戶ID，每一個標簽都是一個獨立的Bitmap。
這樣一來，每一個用戶特征都變得一目了然。
例如，程序員和“00后”這兩個群體，各自的Bitmap分別如下所示。
BitMap好處
1.高性能的位運算
2.相比使用哈希表的話，每一個用戶ID都要用整型數據存儲，少則占用4字節（32bit），多則占用8字節（64bit）。而一個用戶ID在Bitmap中只占1bit，內存是使用哈希表所占用內存的1/32，甚至更少！
3.Bitmap在對用戶群做交集和并集運算時也有極大的便利
如何取反操作呢
我們可以使用異或 運算進行操作，即相同位為0，不同位為1。
同樣是剛才的例子，我們給出“90后”用戶的Bitmap，再給出一個全量用戶的Bitmap。最終要求出的是存在于全量用戶，但又不存在于“90后”用戶的部分。
實現方式
長度計算公式
int nSize = (width * bitPixel + 64) / 64 ;
（高效寫法是(((width * bitPixel + 64)>>6)) )
通過位移操作，可以很方便的擴容
而且越往上就是指數擴容，滿足過億級別數據量的時間復雜度也是O(1)
class MyBitmap:
def __init__(self,size):
self.words=[0]*(self.get_word_index(size-1)+1)
self.size=size
def get_bit(self,bit_index):
if bit_index<0 or bit_index>self.size-1:
raise Exception("超過Bitmap有效范圍！")
word_index=self.get_word_index(bit_index)
return (self.words[word_index]&(1<<bit_index))!=0
def set_bit(self,bit_index):
if bit_index<0 or bit_index>self.size-1:
raise Exception("超過Bitmap有效范圍！")
word_index=self.get_word_index(bit_index)
self.words[word_index] |=(1<<bit_index)
def get_word_index(self,bit_index):
#右移6位，相當于除以64
return bit_index>>6
bitMap=MyBitmap(128)
bitMap.set_bit(126)
bitMap.set_bit(75)
print(bitMap.get_bit(126))
print(bitMap.get_bit(78))
