位操作運(yùn)算的奇技淫巧！(附源碼)

位運(yùn)算

百度百科如下:

程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作

位操作的優(yōu)勢(shì)

• 位運(yùn)算是一種底層的運(yùn)算，往往比我們普通的運(yùn)算要快上許多許多
• 位運(yùn)算是最高效而且占用內(nèi)存最少的算法操作，執(zhí)行效率非常高
• 位運(yùn)算操作的是二進(jìn)制數(shù)，會(huì)擁有一些二進(jìn)制的特性，在實(shí)際問題可以方便運(yùn)用
• 位運(yùn)算只需較低的空間需求
• 位運(yùn)算使用能使程序變得更加簡(jiǎn)潔和優(yōu)美
• 位運(yùn)算可以表示一些狀態(tài)集合

運(yùn)算符號(hào)

下面的a和b都是整數(shù)類型，則：

優(yōu)先級(jí)

C語言中位運(yùn)算符之間，按優(yōu)先級(jí)順序排列為

概念簡(jiǎn)介以及技巧

本文會(huì)以C語言的交互環(huán)境來做代碼演示

常見的二進(jìn)制位的變換操作

and運(yùn)算 &

• 判斷奇偶數(shù)

對(duì)于除0以外的任意數(shù)x，使用x&1==1作為邏輯判斷即可

if (x&1==1)
{
    
}

• 判斷某個(gè)二進(jìn)制位是否為1

比如第7位, 0x40轉(zhuǎn)到二進(jìn)制是0100 0000,代表第7位是1.

if (n&0x40)
{
    //TODO:添加你要處理的代碼
}

• 字節(jié)讀取

(x >>  0) & 0x000000ff	/* 獲取第0個(gè)字節(jié) */
(x >>  8) & 0x000000ff	/* 獲取第1個(gè)字節(jié) */
(x >> 16) & 0x000000ff	/* 獲取第2個(gè)字節(jié) */
(x >> 24) & 0x000000ff	/* 獲取第3個(gè)字節(jié) */

• 判斷一個(gè)數(shù)是不是 22 的指數(shù)

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

• 取余

//得到余數(shù)
int Yu(int num,int n)
{
	int i = 1 << n;
	return num&(i-1);
}

• 指定二進(jìn)制位數(shù)截取

比如說16位二進(jìn)制數(shù)A：1001 1001 1001 1000，如果來你想獲A的哪一位的值,就把數(shù)字B：0000 0000 0000 0000的那一位設(shè)置為1.

比如說我想獲得A的第三位就把B的第三位數(shù)字設(shè)置為1，則B為0000 0000 0000 0100，設(shè)置完之后再把A、B求與， 其結(jié)果若為0，說明A的第三位為0，其結(jié)果為1，說明A的第三位為1.

同理：若要獲得A的第五位，就把B設(shè)置為0000 0000 0001 0000，之后再求與。

通常在我們的程序中，數(shù)字B被稱為掩碼，其含義是專門用來測(cè)試某一位是否為0的數(shù)值。

• 統(tǒng)計(jì)二進(jìn)制中 1 的個(gè)數(shù)

利用x=x&(x-1)，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?，因?yàn)閤-1會(huì)將該位變?yōu)?.

int Count(int x)
{   int sum=0;
    while(x)
    {   sum++;
        x=x&(x-1);
    }
    return sum;
}

or操作

• 生成組合編碼，進(jìn)行狀態(tài)壓縮

當(dāng)把二進(jìn)制當(dāng)作集合使用時(shí)，可以用or操作來增加元素。合并編碼 在對(duì)字節(jié)碼進(jìn)行加密時(shí)，加密后的兩段bit需要重新合并成一個(gè)字節(jié)，這時(shí)就需要使用or操作。

• 求一個(gè)數(shù)的二進(jìn)制表達(dá)中0的個(gè)數(shù)

int Grial(int x)
{
    int count = 0;
    while (x + 1)
    {
        count++;
        x |= (x + 1);
    }
    return count;
}

xor操作

• 兩個(gè)整數(shù)交換變量名

void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

• 判斷兩個(gè)數(shù)是否異號(hào)

int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false

• 數(shù)據(jù)加密

將需要加密的內(nèi)容看做A，密鑰看做B，A ^ B=加密后的內(nèi)容C。而解密時(shí)只需要將C ^ 密鑰B=原內(nèi)容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;
}

• 數(shù)字判重

利用了二進(jìn)制數(shù)的性質(zhì)：x^y^y = x。我們可見，當(dāng)同一個(gè)數(shù)累計(jì)進(jìn)行兩次xor操作，相當(dāng)于自行抵銷了,剩下的就是不重復(fù)的數(shù)

• 找出沒有重復(fù)的數(shù)

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

not操作

• 交換符號(hào)

int reversal(int a) {
  return ~a + 1;
}

• 取絕對(duì)值（效率高）

1. n>>31 取得n的符號(hào)
2. 若n為正數(shù)，n>>31等于0
3. 若n為負(fù)數(shù)，n>>31等于-1
4. 若n為正數(shù) n^0=0,數(shù)不變
5. 若n為負(fù)數(shù),有n^-1 需要計(jì)算n和-1的補(bǔ)碼，然后進(jìn)行異或運(yùn)算，結(jié)果n變符號(hào)并且為n的絕對(duì)值減1，再減去-1就是絕對(duì)值

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在和這個(gè)數(shù)做或運(yù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);

• 進(jìn)行二進(jìn)制逆序

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， 由于優(yōu)先級(jí)關(guān)系，括號(hào)不可省略
}

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的冪指數(shù)

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假設(shè) 8 位。
    return (n + 1) >> 1;
}

• 二分查找32位整數(shù)的前導(dǎo)0個(gè)數(shù)

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) 來實(shí)現(xiàn)

set_bit(char x, int n);

將 x 的第 n 位清0，可以通過 x &= ~(1 << n) 來實(shí)現(xiàn)

clr_bit(char x, int n);

取出 x 的第 n 位的值，可以通過 (x >> n) & 1 來實(shí)現(xiàn)

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 )

綜合應(yīng)用

-END-