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 = (