1. 位運算
百度百科如下：
程式中的所有數在計算機記憶體中都是以二進制的形式儲存的，位運算就是直接對整數在記憶體中的二進制位進行操作，
2. 位操作的優勢
- 位運算是一種底層的運算，往往比我們普通的運算要快上許多許多
- 位運算是最高效而且占用記憶體最少的演算法操作，執行效率非常高
- 位運算操作的是二進制數，會擁有一些二進制的特性，在實際問題可以方便運用
- 位運算只需較低的空間需求
- 位運算使用能使程式變得更加簡潔和優美
- 位運算可以表示一些狀態集合
3. 運算子號
下面的a和b都是整數型別，則：
| 含義 | C語言 |
|---|---|
| 按位與 | a & b |
| 按位或 | a | b |
| 按位異或 | a ^ b |
| 按位取反 | ~a |
| 左移 | a << b |
| 帶符號右移 | a >> b |
| 無符號右移 |
4. 優先級
C語言中位運算子之間，按優先級順序排列為
| 優先級 | 符號 |
|---|---|
| 1 | ~ |
| 2 | <<、>> |
| 3 | & |
| 4 | ^ |
| 5 | | |
| 6 | &=、^=、|=、<<=、>>= |
5. 概念簡介及技巧
本文會以C語言的互動環境來做代碼演示，
常見的二進制位的變換操作：
and運算 &
- 判斷奇偶數
對于除0以外的任意數x，使用x&1==1作為邏輯判斷即可
if (x&1==1)
{
}
- 判斷某個二進制位是否為1
比如第7位, 0x40轉到二進制是0100 0000,代表第7位是1.
if (n&0x40)
{
//TODO:添加你要處理的代碼
}
- 位元組讀取
(x >> 0) & 0x000000ff /* 獲取第0個位元組 */
(x >> 8) & 0x000000ff /* 獲取第1個位元組 */
(x >> 16) & 0x000000ff /* 獲取第2個位元組 */
(x >> 24) & 0x000000ff /* 獲取第3個位元組 */
- 判斷一個數是不是 2 的指數
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
- 取余，(除數為2的n次方)
//得到余數
int Yu(int num,int n)
{
int i = 1 << n;
return num&(i-1);
}
- 指定二進制位數截取
比如說16位二進制數A：1001 1001 1001 1000，如果來你想獲A的哪一位的值,就把數字B：0000 0000 0000 0000的那一位設定為1.
比如說我想獲得A的第三位就把B的第三位數字設定為1，則B為0000 0000 0000 0100，設定完之后再把A、B求與， 其結果若為0，說明A的第三位為0，其結果為1，說明A的第三位為1.
同理：若要獲得A的第五位，就把B設定為0000 0000 0001 0000，之后再求與，
通常在我們的程式中，數字B被稱為掩碼，其含義是專門用來測驗某一位是否為0的數值，
- 統計二進制中 1 的個數
利用x=x&(x-1)，會將x用二進制表示時最右邊的一個1變為0，因為x-1會將該位變為0，
int Count(int x)
{ int sum=0;
while(x)
{ sum++;
x=x&(x-1);
}
return sum;
}
or操作
- 生成組合編碼，進行狀態壓縮
當把二進制當作集合使用時，可以用or操作來增加元素，合并編碼 在對位元組碼進行加密時，加密后的兩段bit需要重新合并成一個位元組，這時就需要使用or操作，
- 求一個數的二進制表達中0的個數
int Grial(int x)
{
int count = 0;
while (x + 1)
{
count++;
x |= (x + 1);
}
return count;
}
xor操作
- 兩個整數交換變數名
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
- 判斷兩個數是否異號
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true
int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
- 資料加密
將需要加密的內容看做A，密鑰看做B，A ^ B=加密后的內容C，而解密時只需要將C ^ 密鑰B=原內容A，如果沒有密鑰，就不能解密！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KEY 0x86
int main()
{
char p_data[16] = {"Hello World!"};
char Encrypt[16]={0},Decode[16]={0};
int i;
for(i = 0; i < strlen(p_data); i++)
{
Encrypt[i] = p_data[i] ^ KEY;
}
for(i = 0; i < strlen(Encrypt); i++)
{
Decode[i] = Encrypt[i] ^ KEY;
}
printf("Initial date: %s\n",p_data);
printf("Encrypt date: %s\n",Encrypt);
printf("Decode date: %s\n",Decode);
return 0;
}
- 數字判重
利用了二進制數的性質：x^y^y = x，我們可見，當同一個數累計進行兩次xor操作，相當于自行抵銷了,剩下的就是不重復的數，
- 找出沒有重復的數
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}
not操作
- 交換符號
int reversal(int a) {
return ~a + 1;
}
- 取絕對值（效率高）
- n>>31 取得n的符號
- 若n為正數，n>>31等于0
- 若n為負數，n>>31等于-1
- 若n為正數 n^0=0,數不變
- 若n為負數,有n^-1 需要計算n和-1的補碼，然后進行異或運算，結果n變符號并且為n的絕對值減1，再減去-1就是絕對值，
int abs(int n)
{
return (n ^ (n >> 31)) - (n >> 31);
}
也可以這樣使用：
int abs(int n)
{
int i = n >> 31;
return i == 0 ? n : (~n + 1);
}
- 從低位到高位.將n的第m位置1
將1左移m-1位找到第m位，得到000...1...000, n在和這個數做或運算，
int setBitToOne(int n, int m)
{
return n | (1 << (m-1));
}
同理從低位到高位,將n的第m位置0，代碼如下：
int setBitToZero(int n, int m)
{
return n & ~(1 << (m-1));
}
shl操作 & shr操作
- 求2的N次方
1<<n
- 高低位交換
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
- 進行二進制逆序
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
- 獲得int型最大最小值
int getMaxInt()
{
return (1 << 31) - 1;//2147483647， 由于優先級關系，括號不可省略
}
int getMinInt()
{
return 1 << 31;//-2147483648
}
- m的n次方
//自己重寫的pow()方法
int pow(int m , int n){
int sum = 1;
while(n != 0){
if(n & 1 == 1){
sum *= m;
}
m *= m;
n = n >> 1;
}
return sum;
}
- 找出不大于N的最大的2的冪指數
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8 // 整型一般是 32 位，上面我是假設 8 位，
return (n + 1) >> 1;
}
- 二分查找32位整數的前導0個數
int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n +16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
- 位圖的操作
將 x 的第 n 位置1，可以通過 x |= (x << n) 來實作
set_bit(char x, int n);
將 x 的第 n 位清0，可以通過 x &= ~(1 << n) 來實作
clr_bit(char x, int n);
取出 x 的第 n 位的值，可以通過 (x >> n) & 1 來實作
get_bit(char x, int n);
如下:
#define clr_bit(x, n) ( (x) &= ~(1 << (n)) )
#define set_bit(x, n) ( (x) |= (1 << (n)) )
#define get_bit(x, n) ( ((x)>>(n)) & 1 )
綜合應用
以下僅列出,感興趣可以參考下面鏈接.
關于操作計數方法
計算整數的符號
檢測兩個整數是否具有相反的符號
計算無分支的整數絕對值（abs）
計算兩個整數的最小值（最小值）或最大值（最大值），而無需分支
確定整數是否為2的冪
標志延伸
- 從恒定位寬擴展的符號
- 從可變位寬擴展的符號
- 通過3個操作從可變位寬擴展符號 有條件地設定或清除位而不分支
有條件地否定一個值而不分支
根據掩碼合并兩個值中的位
計數位設定
- 計數位設定，幼稚的方式
- 計算由查找表設定的位
- 數位集，Brian Kernighan的方式
- 使用64位指令對14、24或32位字中設定的位進行計數
- 并行設定計數位
- 從最高有效位到給定位置的計數位的設定（等級）
- 從給定的計數（等級）中選擇位位置（從最高有效位開始）
計算奇偶校驗（如果設定了奇數位數，則為1，否則為0）
- 天真地計算單詞的奇偶性
- 通過查找表計算奇偶校驗
- 使用64位乘法和模數除法計算位元組的奇偶校驗
- 用乘法計算單詞的奇偶校驗
- 并行計算奇偶校驗
交換價值
- 用減法和加法交換值
- 用XOR交換值
- 用XOR交換單個位
反轉位序列
-
反轉位是顯而易見的方式
- 逐字查找表中的位反轉
- 通過3個操作（64位乘法和模數除法）反轉位元組中的位
- 通過4個操作反轉位元組中的位（64位乘法，無除法）
- 通過7個操作反轉位元組中的位（無64位，僅32位）
- 與5 * lg（N）個運算并行地反轉N位數量
模數除法（又名計算余數）
- 在不進行除法運算的情況下，將模數除以1 << s（顯而易見）
- 在不進行除法運算的情況下以（1 << s）-1計算模數除法
- 不進行除法運算就并行計算（1 << s）-1的模數除法
查找整數的整數對數2（又稱最高位集的位置）
- 使用O（N）運算找到MSB N設定為整數的對數2（顯而易見的方法）
- 查找具有64位IEEE浮點數的整數的整數對數2
- 使用查找表找到整數的對數2
- 在O（lg（N））運算中找到N位整數的對數2
- 使用乘法和查找在O（lg（N））操作中找到N位整數的對數2
查找整數的對數以10為底的整數
查找整數的整數對數10
查找32位IEEE浮點數的整數對數基數2
查找32位IEEE浮點的pow（2，r）根的整數對數基數2（對于無符號整數r）
計算連續的尾隨零位（或查找位索引）
- 線性計算右邊的連續零位（后綴）
- 并行計算右側連續的零位（后綴）
- 通過二進制搜索計算右邊連續的零位（跟蹤）
- 通過強制轉換為浮點數來計算右側連續的零位（跟蹤）
- 用模數除法和查找計算右邊連續的零位（跟蹤）
- 用乘法和查找計數右邊連續的零位（后跟）
通過浮法舍入到2的下一個最高冪
向上舍入到2的下一個最高冪
交織位（也稱為計算莫頓數）
- 交錯位的明顯方式
- 通過表查找交織位
- 帶64位乘法的交織位
-
通過二進制幻數交錯位
測驗單詞中的位元組范圍（并計算出現的次數）
- 確定單詞是否為零位元組
- 確定一個單詞的位元組數是否等于n
- 確定一個單詞的位元組數是否小于n
- 確定單詞的位元組數是否大于n
- 確定單詞是否在m和n之間有一個位元組
按詞典順序計算下一位排列
更多內容可以查看:
http://graphics.stanford.edu/~seander/bithacks.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544938.html
標籤：其他
上一篇：Go字串