位操作的奇淫技巧

本篇参考于
https://zhuanlan.zhihu.com/p/37909700
http://graphics.stanford.edu/~seander/bithacks.html
原文有些内容采用的是c语言，我尽我所能改为java，由于c语言和java在设计上有不同的部分，所以不能保证效率如原文实现的那样。其中一些比较难的部分，我选择跳过~

二进制运算规律

首先得了解最基本的微操作的规律：
～x = -x - 1：从以上0与-1的按位关系可以看到，两者的二进制位正好取反；此规律能推广到1与-2，2与-3……等等。因此，该性质是not操作中最常使用的性质。
(~x)&x = 0：任意数与它的取反数的and操作结果为0。
(~x)|x = -1：任意数与它的取反数的or操作结果为-1。
(~x)^x = -1：任意数与它的取反数的xor操作结果为-1。
x|0 = x：任意数x与0的or操作结果为x自己。
x^0 = x：任意数x与0的xor操作结果为x自己。
x^yy = x：任意数x与任意数y进行两次xor操作结果为x自己。
值得注意的是对于|，&，^操作满足各自的结合律和交换律，也就是说多个数或，与，异或操作（注意不能混合），是可以任意交换次序的。而~操作满足自反律。（x=~~x）

一些常用的位操作技巧

在做一些比较复杂的判断之前，先来做一些简单的题目。

&操作部分：

image.png

显然也可以用一个新的变量把这个数存下来，然后向右移位N-1位再&1>0则为1，不然为0。但显然多使用了一个变量肯定没有前面那种方式好。

image.png

也许你会问：以上两个操作有什么意义呢？稍后在“把二进制码当作集合使用”会揭晓。

image.png

我自己的理解是：要注意返回值，read（）的返回值虽然是int，但是是读取的byte&0xff得到的。这个过程由于符号拓展，前24位全为byte的符号位，而当byte的值全为1（十进制为-1）时，这个返回的int值也就变成了-1。而使用io流一般都是以while(input.read() != -1)作为条件的，如果返回的int值为-1，显然会结束io流的使用，而这显然不是程序的本意。所以为了避免流操作数据提前结束，将读到的字节进行int类型的扩展时，采用&0xff方式，由符号拓展变为0拓展，避免出现int值为-1的情况（此时为255）。而真正返回-1的判断条件是pos>=count。相似的应用还有很多，只要牵扯到在默认使用符号拓展时不满足需求，需要改为0拓展时，都可以将原来较小的数据&0xff..（f个数与数据字节数*2相同）。

image.png

（图中Encoder类是BASE64的静态内部类）

这里必须先引入BASE64的原理
https://www.choupangxia.com/topic/detail/61
要注意原博客图，a表示的二进制数不是8位，少了一位，应该是写错了。

image.png

这里代码第一行指截取8位的前6位，第二行指将8位的后两位移到第三位和第四位上去。第三行第四行直接用'='置位。也就是通过以上代码，将如下图所示的的文本"A"变成了规范的BASE64编码。

image.png

or操作部分：

image.png

把字节部分X和字节部分Y合并为原来字节时，先取X的最低两位，左移四位，其余位置0；取Y的最高4位，右移四位，去掉符号位。X和Y取或操作，产生的新数的第五六位是X的最低两位，最低四位是Y的最高四位。如下图

image.png

其实就是通过B,C把k表示出来，显而易见Q就是B的前6位，M就是C的后四位在最后补0。在把两各数的特定位数组合起来时，通常用|操作。

xor操作

首先是一个交换两个数的值的例子。
第一种方案,增加临时变量:

void swap(int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

这种方案的弊端就是临时变量占用内存开销.

第二种方案,采用加减法或者乘除法:

void swap(int x, int y)
{
  x += y;
  y = x - y;
  x -= y;
  /* 下面是乘除法
  x *= y;
  y = x / y;
  x /= y;
  */
}

这种方案的弊端是有溢出风险.

第三种方案,采用异或:

void swap(int x, int y)
{
  x ^= y;
  y ^= x;
  x ^= x;
}

这种方案的代码看起来甚是清爽,但是暗藏杀机看出来了吗?
异或最大的问题是如果两个值相等,异或为0.这种方案在x和y相等的情况下失效.当然,解决也很简单,在代码开头加上判断

void swap(int x, int y)
{
  if(x == y) return;
  x ^= y;
  y ^= x;
  x ^= x;
}

以上三种方法都有一个问题,那就是函数的值传递问题,如果在main函数里调用以上的swap函数,传递过来的其实是实参的值,swap函数交换的只是形参,对实参没有任何影响(C语言、Java语言都一样).所以,一般在c语言里边交换函数会这么写:

void swap(int *x, int *y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}
或者这么写:

void swap(int *x,int *y){     
    (*x) ^= (*y) ^= (*x) ^= (*y);     
}  

采用指针传递地址,完美地解决了函数值传递的问题。
但是对于java而言，因为只有值传递。所以当参数为基本数据类型，在方法中对其做的任何修改是没有意义的。当参数为引用数据类型，方法中是可以修改引用的对象的状态的，但无法改变其引用指向的对象。所以是无法通过调用swap方法改变两个基本数据类型的值的。

image.png image.png

再看一个经常被笔试的例子:求两个数x和y的平均数.

很容易想到的答案是(x+y)/2.
但是这个答案有个问题,x+y有溢出风险,于是一部分人在第一个答案的基础上优化了一下,演变成 x+(y-x)/2,其实这是在自作聪明,题目里根本没告诉你x和y同符号,y-x照样有溢出风险。
综合前面的情况,我们想到了方案,在判断x和y符号位相异的情况下返回第一个答案,符号位一致的情况下返回第二个答案.答案倒是对了,但着实麻烦,以至于我都懒得写出来。
用位运算解决这个问题很简单,当然不是(x+y)>>1啦,是(x&y)+(x^y)>>1。

第一次见可能觉得不太好理解,思路其实非常直观,它把x和y的二进制补码按位分成两种情况,一种值相同(x和y该位皆为0或者1),一种是相异(x为0、y为1或者x为1、y为0)。
对于值相同的位,(x&y)相当于x和y该位之和除2;对于值相异的位,x和y该位取异或相当于该位求和,再右移一位相当于除2.两者相加就是平均数.当然这里我没有写出来当值相异时(x&y)为0,以及当值相同时(x^y)也为0,0对加法结果不产生任何影响。

not操作

数组逆序遍历时可以采用如下写法：

    for(int i=0;i<a.length;i++){
        System.out.println(a[a.length+~i]);//~i=-i-1
    }

移位操作

左移：

image.png

右移：

image.png

关于运算次数的统计方法

当讨论到计算某个算法的运算次数时，任何一个C语言的运算符都会被统计为一次运算。中间变量的赋值，即不需要写入到内存中的赋值操作，不会被统计在内。当然，这种统计方法只能得到综合机器指令和CPU时间的一个近似值。影响一段程序在系统中的运行时间的因素非常多，比如缓存大小，内存带宽，不同的指令集等等。所有运算消耗的时间相同在现实中是不成立的，但是CPU技术随着时间的推移，正在往这个方向飞速发展。总的来说，想要判断一种方法比另一种方法更快，最好的方式是直接到你的目标机器上去跑基准测试，测试性能的优异。

计算整数的符号

注意：在java中基本数据类型大小固定，没有sizeof关键字，只需要算术右移所需数据类型所占位数减1即可获得符号位。

int v; // 我们需要找到这个数的符号
int sign; // 结果存在这⾥
// ⽅法1：⾥不使⽤ if 以避免在 CPU 上的分⽀跳转
sign = (v < 0)?-1:0; // if v < 0 then -1, else 0（0包括正数和0的情况）
// ⽅法2：
sign = v >> (32 - 1);