閱讀796 返回首頁    go 阿裏雲 go 技術社區[雲棲]

編程珠璣之1.2位邏輯運算實現位向量

    所謂位向量就是由一些二進製位組成的向量，位邏輯運算有與（&）.或（|），非（！），移位（<<  >>）等。

   使用位邏輯運算實現位向量所指實現位向量的設置，清零以及探測功能。

#define BITPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1+N/BITPERWORD]

//設置數組第i位為1
void set(int i)
{
        a[i>>SHIFT] |= (1<<(i&MASK));
}

//清空數組第i位為0
void clr(int i)
{
        a[i>>SHIFT] &= ~ (1<<(i&MASK));
}
//查詢數組第i位數字
void test(int i)
{ 
     return a[i>>SHIFT] &(1<<(i&MASK));
}

算法解析：
1.set算法中i>>SHIFT相當於i/32,也就是2^5,功能是找出i對應數組中到哪一行，每一行都是32Bit,需要將相應到位置置為0或者1；需要1<<(i&MASK),其中i&MASK是計算需要左移的位數，然後把1向左移動這麼多位，剩下的就是和數組中的元素或運算。set算法可以改寫為：

void set(int i)
{
        a[i/32] |= (1<<(i%32));
}

2.clr算法中通過1<<(i&MASK),其中i&MASK是計算需要左移的位數，然後把1向左移動這麼多位，然後把該數字取反，和數組中到元素與運算，即可置第i位為0.clr算法可以改寫為：

void clr(int i)
{
        a[i/32] &= ~ (1<<(i%32));
}
3.test算法中通過1<<(i&MASK),其中i&MASK是計算需要左移的位數，然後把1向左移動這麼多位，然後把和數組中到元素與運算，數組中元素為1就返回1，數組中元素為0就返回0.test算法可以改寫為： 


void test(int i)
{
        return a[i/32] &(1<<(i%32));
}


最後更新：2017-04-04 07:03:27

  上一篇：go android Setting中隱藏項
  下一篇：go 【最近麵試遇到的一些問題】JAVA UTF-8 GB2312 編碼互轉