最近发现位运算在很多场合有很多运用啊。大概有以下几个方面:
- 涉及二进制及其2^n进制的运算
- 很少字段的struct class的改写例如棋盘记录和模式比较
- 逼格&效率比较高的小心机
几个运算符
| 符号 | 名称 | 含义 |
|---|---|---|
^ |
按位亦或 | 同为0，异为1 |
| $\mid $ | 按位或 | 有1则1，双0为0 |
& |
按位与 | 有0则0，双为1 |
~ |
按位取反 | 变1为0，变0为1（包含符号位） |
<< |
按位左移（包括符号） | 二进制每移一位乘二,最右补零 |
>> |
按位右移（包括符号） | 二进制每移一位除二,无符号最左补零，有符号补符号位 |
`>>> |
按位无符号右移 | 对应二进制全指定的位数 |
以上均是按位操作，要区分逻辑运算&& ||和位运算符& |
关于取反
普通的Integer char等按位操作都是直接按照它们的二进制补码操作，int直接使用该数字的补码，char则先按照ascii转换成二进制在进行操作。
e.g.char a = 'a'a的ascii码十进制为097，二进制原码为1100001，这里注意，作为char，它在java中是一个无符号16位的整数，所以补齐它的
二进制原码 补码 反码（非负数原码 补码 反码相同）
000000000 1100001
取反后的补码
111111111 0011110
取反后的反码
111111111 0011101
取反后的源码
100000000 1100010
十进制即为 -98。
同理的，byte如果存储字符型也是按照先转成ascii码进行操作，即便是字符型的数字也一样。
byte a = 2;
int b = ~a;//输出b为-3
byte c = '2';
int d = ~c;//输出d为-51 2的ascii为50(十进制) 32(十六进制)
关于亦或
亦或相当的特别同时阴森啊，有几个性质
- a^a = 0 也就是亦或自己为0，因为每位都是相同的。
- a^a^a = a^0 = 0^a = a
- a^b = b^a 符合交换律
- (a^b)^c = a^(b^c) 符合结合律
- e = a^b^c^d <-> e^a = b^c^d <-> e^a^b= c^d <-> e^a^b^c=d
既然满足交换律结合律，则如果出现这么一种情况，
[一个数组里除了一个数值出现一次，其他都出现了两次。找出这个数值。]
将这个数组全部亦或一遍，则出现两次的都可以按照交换律结合律化为0，
数组内只存在两个奇数次出现的数，其他都出现了偶数次，找出这两个数
思路：这就是上面实例的改进，因为知道了其他数字都出现了偶数次，全体亦或的结果就是
x=a^b其中a b分别是所要找的这两个数。由于a b不同，则x必然不为零，也必然存在为1的位（可以取从右第一次出现1的位置）。同时由于是亦或操作，这个1必然是a和b相异造成的。这样，把这一位为1的分一组，这一位为0的分一组，出现偶数次的依然会被分到一组通过亦或自己消除。
//从右寻找补码中1第一次出现的位置
public static int getFirst1(int num){
int index = 0;
while(index<32){//Integer有32位
if(((num&(1<<index))^(1<<index))==0)
return index+1;
else
index++;
}
return -1;
}
//判断这个数这一位是否为1
public static boolean is1AtPos(int num,int pos){
return ((num>>(pos-1))&1)==1;
}
//寻找这两个数
public static int[] get2Num(int[] a){
int [] find2Num = new int[2];
//默认初始化0
int rs = 0;
for (int i : a) {
rs ^= i;//亦或全体求x
int pos=getFirst1(rs);//寻找第一个出现1的位
for (int j : a) {
if(is1AtPos(j,pos))//按这位是否位1分组
find2Num[0] ^= j;
else
find2Num[1] ^= j;
}
System.out.println(find2Num[0]+" "+find2Num[1]);
return find2Num;
}
使用位亦或^节约空间的数据交换
原理：a亦或b=c，b亦或a=c，也就是亦或满足交换律；位亦或的逆运算，也就是(a^b)^b=a等于它自己。所以，只需三个亦或运算即可交换数据。看代码。
a ^= b;
b ^= a;
a ^= b;
使用亦或加密
中文配合亦或加密再加上其他的一些加密算法可以很好的掩护原文。
char a1='晚' , a2='上' , a3='来' , a4='我', a5='家' ;
char secret='8' ;
a1=(char) (a1^secret);
a2=(char) (a2^secret);
a3=(char) (a3^secret);
a4=(char) (a4^secret);
a5=(char) (a5^secret);
System.out.println("密文:"+a1+a2+a3+a4+a5);
a1=(char) (a1^secret);
a2=(char) (a2^secret);
a3=(char) (a3^secret);
a4=(char) (a4^secret);
a5=(char) (a5^secret);
System.out.println("原文:"+a1+a2+a3+a4+a5);
亦或判别IP地址是否相等
使用亦或在加上按位与的方式比==加&&的方式效率高。
static int ipv6_addr_equal(int[] in6_addr_a1, int[] in6_addr_a2)
{
return (((in6_addr_a1[0] ^ in6_addr_a2[0]) |
(in6_addr_a1[1] ^ in6_addr_a2[1]) |
(in6_addr_a1[2] ^ in6_addr_a2[2]) |
(in6_addr_a1[3] ^ in6_addr_a2[3])) == 0);
}
关于按位与
按位与操作一般是与1配合 判断奇偶，或者判断某位是否为1；或保留下某位位数字(与位移结合)
a&1 == 0 偶数
a&1 == 1 奇数
关于按位与
按位或操作一般与0配合
按位左右移
左右移本质上就是以bit为单元进行二进制的操作，而二进制左右移n位在十进制就意味着乘以2^n或除以2^n.按位操作可以大大提升效率
港真，很多面试都有求幂的题目。很棒，刷题狗就喜欢做这种题，然而第一次碰到这题我懵逼的采用了树。傻缺了。
将二进制数绕圈循环，取往左(右)第k个为头。很多题目里面有啊
int a = a<<k | a >> (Integer.SIZE-k); //左数第k个当头
int b = b>>k | b >> (Integer.SIZE-k); //右数第k个当头
第k位置1
a|(1<<k);
第k位置0
a&(~(1<<k));
取第k位的数值
a>>k&1;
后k位为0，其余为1
(~0)&(1<<(k+1));
后k位为1，其余为0
~((~0)<<k);
左右移应用-二分求幂
Caution！这个思想很重要!
思路：求a^b，如果b是一个2的整数幂，举个栗子，32，那可以进行这样的迭代，由于$32=2^5$,那么就可以这样求，
- 第一次求 $a_1=a^2$
- 第二次求 $a_2=a^4=a^{2*2}={a_1}^2$
- 第三次求 $a_3=a^8=a^{4*2}={a_2}^2$
- 第四次求 $a_4=a^{16}=a^{8*2}={a_3}^2$
- 第五次求 $a_5=a^{32}=a^{16*2}={a_4}^2$
如果是通过迭代幂的次数，需要32次才能达到，然而通过分治的方式，只需要5次就能解算32次幂。那如果不是2的整数幂次方呢，很好办，通过将该整数分解成各个2的整数次幂的和，例如求取a的23次方,又$23=16+4+2=1$，所以原式可化为$a^{2^4+2^2+2^1+2^0}$,通过二分的方式，变形为$$(a^{16})\cdot (a^4)\cdot (a^1)\cdot (a^0)$$.
显然！上式就是二进制和十进制转换的过程，通过4+2+1=7次计算就可解出，而非单循环的23次。
其实，解算a的16次方中，即可用到$${a^4}^{2^2}$$,即计算a^的16次方只需用到2步，总共2+2+1=5次迭代就可计算完毕。
因而解决a^b次幂的步骤是
- 将幂次化为2进制
- 从低位遍历，为1则乘以当前幂次，为0则计算当前幂次，然后跳过，直接移至下一位
- 当幂指数的二进制推到最高位
public static long Power(int a, int n){
long ans = 1;
System.out.println("幂指数二进制："+Integer.toBinaryString(n));
while (n > 0) {
if ((n & 1)!=0) {//末位不为零
ans *= a;
}
a *= a;//计算当前幂次
n >>= 1;//迭代每次推一位
}
return ans;
}
递归版本可能更清晰
public static int power(int a,int n) {
if(n==1) return a;
if(n&1)
return power(a,n-1) * a;
else
{
int t=power(a,n>>1);
return t*t;
}
}
下面还有更炸裂的
利用位移求二进制里1的奇偶
一般的思路就是，一位一位截末位，为1则亦或一下，为0则不管。对于Integer需要循环32次，对byte需要循环8次。
1数量为奇则返回1，为偶数则返回0。
public static int get11Count(int x){
int i=0;
for(int j =0 ;j<32;j++){
if((x&1)==1)
i ^= x&1;
x >>= 1;
}
return i;
}
但四，这个方式没有体现位移的优越性。通过分治的思想，由于结果只求1或0，那么通过1位表达2位的信息，通过2位表达4位的信息，通过4位表达8位的信息，通过8位表达16位的信息，通过16位表达32位的信息。通过五次表达，就可以求出结果。
最关心的，其实只是最后一位
先看代码
public static int get1Count(int x){
//返回二进制数有偶数还是奇数个1 偶数返回0 奇数返回1
x = x ^ (x >> 1);
x = x ^ (x >> 2);
x = x ^ (x >> 4);
x = x ^ (x >> 8);
x = x ^ (x >> 16);
return x&1;
}
解析一下。先拿byte举个栗子。因为byte是1个字节8个bit，所以表达-128~127即$-2^7\sim 2^7$.按照上面的方式，只需右移三次.举个例子88，二进制为$2^6+2^4+2^3=1011000$
第一次
01011000
00101100
xor --------
01110100 ->这个是结果！
结果的数值含义是，将原式中，这一位i与该位的上一位(即第i+1位)做了一次亦或，结果式中每出现一个1，则代表原式中必然邻位相异。其实，由于最终结果只需要表述奇偶，因此两个1为0，等同于抵消的含义。
第二次亦或
01110100
00011101
xor --------
01101001 —>第二次的结果
结果的含义是，每一个数字1表示##原式##中，每一位与其前3位二进制数值中1的个数为奇数；每一个数字0表示##原式##中，每一位与其前3位二进制数值中1的个数为0.
第三次亦或
01101001
00000110
xor --------
01101111 ->第三次结果
显而易见，每个1的出现表示与其前7个数字1出现奇数次。
最后取最后一位x&1,得到1，即原式中有奇数次1.结果正确。
进阶-计算二进制1的个数
最原始的方式
int BitCount(unsigned int n)
{
unsigned int c =0 ; // 计数器
while (n >0)
{
if((n &1) ==1) // 当前位是1
++c ; // 计数器加1
n >>=1 ; // 移位
}
return c ;
}
原始方式的改进
int BitCount1(unsigned int n)
{
unsigned int c =0 ; // 计数器
for (c =0; n; n >>=1) // 循环移位
c += n &1 ; // 如果当前位是1，则计数器加1
return c ;
}
亦或清1法
int BitCount2(unsigned int n)
{
unsigned int c =0 ;
for (c =0; n; ++c)
{
n &= (n -1) ; // 清除最低位的1
}
return c ;
}
查表法1：
int BitCount3(unsigned int n)
{
// 建表
unsigned char BitsSetTable256[256] = {0} ;
// 初始化表
for (int i =0; i <256; i++)
{
BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2];
}
unsigned int c =0 ;
// 查表
unsigned char* p = (unsigned char*) &n ;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
return c ;
}
查表法2：4bit查表
int BitCount4(unsigned int n)
{
unsigned int table[16] =
{
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
} ;
unsigned int count =0 ;
while (n)
{
count += table[n &0xf] ;
n >>=4 ;
}
return count ;
}
查表法3：8bit查表
int BitCount7(unsigned int n)
{
unsigned int table[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};
return table[n &0xff] +
table[(n >>8) &0xff] +
table[(n >>16) &0xff] +
table[(n >>24) &0xff] ;
}
###炸裂的平行算法
邻位相加，重复这一过程，直到只剩一位。
#include <stdio.h>
#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
int x;
while (cin >> x) {
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
cout << x << endl;
}
return 0;
}
###终极大招
int BitCount5(unsigned int n)
{
unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111);
return ((tmp + (tmp >>3)) &030707070707) %63;
}
补充：位标志法
struct _byte
{
unsigned a:1;
unsigned b:1;
unsigned c:1;
unsigned d:1;
unsigned e:1;
unsigned f:1;
unsigned g:1;
unsigned h:1;
};
long get_bit_count( unsigned char b )
{
struct _byte *by = (struct _byte*)&b;
return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h);
}
求二进制最高位前0的个数
int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n += 16; x <<= 16;}
if ((x >> 24) == 0) {n += 8; x <<= 8;}
if ((x >> 28) == 0) {n += 4; x <<= 4;}
if ((x >> 30) == 0) {n += 2; x <<= 2;}
n = n - (x >> 31);
return n;
}
二进制逆序
int change(int x)
{
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
return x;
}
位移求绝对值
x xor (not (x shr 31) + 1) + x shr 31
x = x ^ ((~(x>>31))+1) + x>>31;
交换二进制高16位和低16位
int change(int x)
{
return (x >> 16) | (x << 16);
//byte可写成(x >> 4) | (x << 4);
}
参考链接：