位运算操作[Java语言描述]

原创

开胃狼

修改于 2019-11-18 17:24:37

1.1K0

修改于 2019-11-18 17:24:37

文章被收录于专栏：编程语言基础编程语言基础

0. 注意

阅读本文之前，务必搞清楚计算机中有关源码，补码的相关概念，位运算 & (按位与) | （按位或） ~ （取反） ^ （异或）相关概念和操作

1. 计算某个Long类型正数二进制表示法中1的个数

理论

Java中各种进制的表示方法：
- 二进制 0B1010_1000 【以0B ，或者 0b （第一个是零，b不区分大小写）】
- 八进制 0123456 【以零开头】
- 十六进制 0X12AB 【以零x开头，x不区分大小写】

对于一个数X，表达式 X & (X-1) 的含义是 : 将X（二进制）最右边的1 清零，即把最右边的 1 设置为 0 。

举例(以整数为例，Java中一个整数占用4个字节，下划线是为了方便查看，Java编译器支持这种写法)：

x = 8 (0B0000_0000_0000_1000)

x-1 = 7 (0B0000_0000_0000_0111)

8&7 (0B0000_0000_0000_0000)

对比 8&7 与 8 的二进制，发现最右边的 1 已经变成0 了

x = 7 (0B0000_0000_0000_0111)

x-1 = 6 (0B0000_0000_0000_0110)

7&6 (0B0000_0000_0000_0110)

对比 7&6 与 7 的二进制，发现最右边的 1 已经变成0 了

代码：不停的将target最右边的1 清零，清零一次，计数一次，直到 target为0为止。

public int countOne(long target){
        int result=0;
        for(;target!=0;result++){
            target &=target-1;
        }
        return result;
    }
    @Test
    public void test1(){
       long target= 8L;
        assertEquals(1,countOne(target));//OK

        target=7L;
        assertEquals(3,countOne(target));//OK
    }

2. 判断（二进制表示）某一位上是0还是1

思路： int 类型数 119 （0B0000_0000_0111_0111‬）,Java中是4个字节32位。从左往右，高位在左，底位在右（与10进制表示一样）

第5位（位数从0开始）的值是 1，如何判断？这要用到左移操作，数字 1(0B0000_0000_0000_0001 因为Java中的byte,char,short,运算的时候会自动提升为int类型，所以用4个字节表示)左移1位就是：0B0000_0000_0000_0010,即 1_2^1 其实就是 2，左移2位就是 0B0000_0000_0000_0100 ,即 1_2^2, 为4 （左移位补右边补0，左边被挤掉丢弃），移到第5位的位置需要左移5次，即

0B0000_0000_0010_0000，而 119是

0B0000_0000_0111_0111, 现在将这两个数按位与（&），其结果为：

0B0000_0000_0010_0000

假设第5位上的不是1，而是0，那么最后的结果一定全部都是0

所以可以认定：最后的结果如果不是0，那么这一位是肯定是1，如果是0，那么这一位上就一定是 0

根据这个思路，代码如下：

	public boolean getBit(Long target,int offset){
        // 这里一定要写成 1L,后面2.1 小节会解释
        return (target & 1L<<offset)!=0;
    }
    @Test
    public void test2(){
        long target= 119L;
        assertTrue(getBit(target,5)); //OK

        target=0B0000_0000_0101_0111;// 87
       assertFalse(getBit(target,5)); //OK
    }

2.1 Java中关于左移的一个坑

首先看一段代码：

@Test
public void test2_1(){
    int resultInt=1<<31;
    //打印result的二进制表示
    //输出: 10000000000000000000000000000000
    System.out.println(Integer.toBinaryString(resultInt));

    long resultLong= 1<<63;
    //输出:1111111111111111111111111111111110000000000000000000000000000000
    System.out.println(Long.toBinaryString(resultLong));
}

第3行代码，因为移动了31位，在整数的范围内，所以用整数接收结果，输出的结果没有问题。

但是下面的移位63，输出的结果并不是预期的结果，预期的结果应该是第 63位（最左边的最高为）为1，其余全部是0才对，为什么中间多了好多1？

原来Java中左移运算符<< 在运算的时候是有要求的。JVM会检查数据类型，也就是检查 1 ，发现是int类型的，int是4个字节32位，那么它会做 63%32 运算，结果是31，这个31才是真正要左移的位数

上面的代码 1<<63, 其实真正左移了31位，就变成了10000000000000000000000000000000 ,它是个32位的整数，最高位为1，现在要将这个整型的值赋值给一个long类型（类型自动提升），为了不改变这个数值（它是个负数，最高位为1），在前面补上了32个1，这就是第10行输出的结果。

搞清楚了运算符 << 的规则后，代码做如下改变就可以得到我们想要的结果：

 long resultLong= 1L<<63;

只需要在1后面添加一个 L或者是l(小写)，表明 1 现在是一个 long类型的，那么移位之前，做 64%63，结果是 63，这才是真正要移动的位数

    @Test
    public void test2_1(){
        int resultInt=1<<31;
        //打印result的二进制表示
        //输出: 10000000000000000000000000000000
        System.out.println(Integer.toBinaryString(resultInt));

        long resultLong= 1<<63;
        //输出:1111111111111111111111111111111110000000000000000000000000000000
        System.out.println(Long.toBinaryString(resultLong));

        resultLong= 1L<<63;
        //输出:1000000000000000000000000000000000000000000000000000000000000000
        System.out.println(Long.toBinaryString(resultLong));
    }

3. 将二进制表示的某一位设置为1

第i 位（i从0开始）和0 或 (|) 保持不变，和1 或(|) 变成1，所以代码如下：

    public long setBitTrue(Long target, int offset){
        //注意1后面有一个L表示它是一个long类型的
        return target | 1L<<offset; 
    }
    @Test
    public void test3(){
        //注意这是long类型，共8个字节
        long target=0B0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001L; //1
        assertEquals(3,setBitTrue(target,1));  //OK,结果是3

        //注意long类型的最高位是 63，同时也是符号位,这里只是将15位上设置成1了，符号位并没有改变
        assertEquals(32769,setBitTrue(target,15)); //OK，结果是32769

        //输出 1000000000000000000000000000000000000000000000000000000000000001
        System.out.println(Long.toBinaryString(setBitTrue(target,63)));

        //这里改变最高位，第63位为1，这个是符号位，由 0 变成了1，变成了负数
        //如果不明白这句话，需要补脑源码，补码的相关知识
        assertEquals(-9223372036854775807L,setBitTrue(target,63));
    }

那么问题来了，为什么是 -9223372036854775807 ?

首先看 long类型的1 在内存的表示是：

0B0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001 (8字节，64位)

最高为，第 63位置为1 后的结果是：

0B1000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001

计算机中存储的数字二进制都是以补码的形式存放的，最高位为1,即符号位为1，那它必定是一个负数，那它的值是什么？将这个值取反后+1 就是这个数的绝对值（正数表示）,也就是：

0B0111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111, 可以直接用代码：

System.out.println(0B0111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111L)

上面代码输出: 9223372036854775807 ,因为最高为是1，是一个负数，所以最终的结果就是-9223372036854775807

4. 将二进制表示的某一位设置为0

要将一个数如 -1 （0B1111_1111_1111_1111_1111_1111_1111_1111） ,整数，四个字节的第0 为设置为1，只需要与

                           0B1111_1111_1111_1111_1111_1111_1111_1110 做 & 操作即可，因为 和 1与（&） 不变， 和 0 与（&） 就会变成0 。

问题是如何得到 0B1111_1111_1111_1111_1111_1111_1111_1110 呢？这个简单，只需要得到 0B0000_0000_0000_0000_0000_0000_0000_0001 , 然后取反 (~ 大键盘数字键1左边的那个键)

代码如下：

    public long  setBitFalse(Long target,int offset){
        long mask= ~(1L<<offset);
        return target & mask;
    }
    @Test
    public void test4(){
        long target=-1;
        //把第1位由1变成0， 相当于 -1，所以最终的结果是 -2
        assertEquals(-2,setBitFalse(target,0));
    }

5. 判断二进制表示的哪些位为1

如一个int类型的整数 10(4个字节)，二进制表示为： 0B0000_0000_0000_0000_0000_0000_0000_1010 ，为1的位有: 3,1

因为一个int类型的占用4个字节，共32位，要判断有哪些位为1，只需要不断的做无符号右移操作,每次判断最末尾是否是1即可。

代码如下：

    public int[] getBitOffsets(Long target){
        //调用前面的contBit方法确定有多少个1
        int[] result=new int[contBit(target)];
        int resultOffset=0;

        //不停的做无符号右移,为0的时候循环结束
        for(int i=0;target!=0;i++){
            if((target & 1L)==1L){
                result[resultOffset++]=i;
            }
            target >>>=1;
        }
        return result;
    }

    @Test
    public void test5(){
        long target=10L;
        System.out.println(Long.toBinaryString(target));//1010

        int[] result=getBitOffsets(target);
        assertArrayEquals(new int[]{1,3},result); //OK

        target=-1L;// 64个1
        //输出 [0,1,2...63] 也就是所有位上都是1
        System.out.println(Arrays.toString(getBitOffsets(target)));
    }

6. 应用场景

6.1 整数排序

需求：假设有一个整数序列，序列中的每个值都不超过64，而且值没有重复，序列的长度最长为64，现在对这个序列进行排序。

因为序列的长度不超过64，序列中的每个值都不超过64，而long类型刚好是64位，所以就可以将要排序的序列"映射"到二进制的序列上。比如要排序的序列是： {34,56,23,45,24,15,14,10,3,16}，映射结果如下：

图中只标注了1，其余不存在的数字均标记为0，上图为了保持整洁，并没有画出

代码:

    @Test
    public void test6_1(){
        int[] targetArray={34,56,23,45,24,15,14,10,3,16};

        long bitMap=0;//所有的二进制位全部置为0

        for(int item:targetArray){
            bitMap=setBitTrue(bitMap,item);
        }
        System.out.println("排序结果：");
        System.out.println(Arrays.toString(getBitOffsets(bitMap)));
    }

6.2 大数据量排序

上面的排序实际中很少用到，但是提供了一个BitMap(按位映射)的思路。假设最多有 200 亿个long类型的数据需要排序，那么该如何来排序？

首先考虑这200 亿个数据存储的问题，假设存储到文件中，那么这个文件有多大？

200 亿 8 字节= 200 10^8 8 字节=1600 10 ^8 字节=1562.5 10^5 KB = 1525.87890625 10^2 MB = 152587.890625MB =149.011GB, 这个数据将近149 G，很显然要将这么庞大的数据读入内存再排序是不可能的。

那如果使用 200 亿个比特位来映射这些数据呢？看看需要多少内存？

200 10^8 比特位 = 200/8 10^8 字节= 25 10^8 字节 = 24.414 10^5 KB = B= 23.8418* 10^2 MB = 2.3283GB

也就是说 200亿个比特位占用不到 2.4 G 的内存，这个用一般的PC机内存是可以存储的。

但是这么长的比特位在Java中如何构建出来呢？Java中提供了一个类 java.util.BitSet, 可以将它看成是一个可变长的比特位序列，每个元素都是一个boolean类型的值，其实就是 0和1 ，我们可以创建一个BitSet实例对象，然后将这200亿个数字映射到序列上，数字就是索引号，数字存在该索引号对应的值就是1，不存在对应的就是false。

下面对20个long类型的数据使用 BitSet进行排序：

 @Test
    public void test6_2(){
        long[] targetArray={32424L,4324324L,243123412L,223423L,54564L,64767L,7476L,432143L,67L,647L,
        8657L,5765L,654L,7654L,345L,7658L,979L,2345L,85876L,2354L};

        BitSet bitSet=new BitSet(targetArray.length);
        for(long item:targetArray){
            bitSet.set(Long.valueOf(item).intValue());
        }
        //bitSet 中最高的索引+1， 因为bitSet的索引从0开始的
        // int maxIndex= bitSet.length();

        int first=bitSet.nextSetBit(0) ;//返回第一个设置为 true 的位的索引，这发生在指定的起始索引或之后的索引上。如果没有则返回-1
        for(;first>0 ;first=bitSet.nextSetBit(first+1)){
            System.out.print(first+" ");
        }
        //输出 ： 67 345 647 654 979 2345 2354 5765 7476 7654 7658 8657 32424 54564 64767 85876 223423 432143 4324324 243123412 
    }

使用这种 BitMap的方法来判断元素是否存在重复也非常的容易，如果索引对应的值为true，表示这个值已经存在了。

同时 BitSet 也支持 &与 , |或 , ^异或 , 的操作，分别使用对应的方法（and， or ， xor ），详情请参考 API文档

BitSet 内部的二进制序列实际上是由多个 long类型的整数组合而成的。6.3 连续签到场景

现在的app上都有签到的场景。每日签到，如果连续7日签到，获得送积分或者送优惠券的奖励。先假设如下的条件：

某app用户不超过 64人，id编号从0 开始（实际场景的用户数要远比这个数大，这里只设置简单场景），连续签到3日可获得奖励。

准备3 个long数据用来存储每日签到，它的二进制序列的索引对应用户编号，签到则将对应的二进制位置为1
要判断是否连续签到，只需要将 3个long类型的值做 &（与）运算，得到的结果就是这3天连续签到的用户

id为13和10 的用户连续3日签到。

@Test
    public void test6_3(){
        long[] days={0,0,0}; // 3个long类型的二进制序列
        days[0] = setBitTrue(days[0],2); // 调用前面定义的方法
        days[0] = setBitTrue(days[0],10);
        days[0] = setBitTrue(days[0],13);  //第一天 2,10,13 号用户签到

        days[1] = setBitTrue(days[1],0);
        days[1] = setBitTrue(days[1],7);
        days[1] = setBitTrue(days[1],8);
        days[1] = setBitTrue(days[1],10);
        days[1] = setBitTrue(days[1],13);  //第二天 0,7,8,10,13 号用户签到

        days[2] = setBitTrue(days[1],3);
        days[2] = setBitTrue(days[1],10);
        days[2] = setBitTrue(days[1],13);
        days[2] = setBitTrue(days[1],14);
        days[2] = setBitTrue(days[1],15);  //第三天 3,10,13,14,15 号用户签到

        //求连续签到列表
        long result= days[0] & days[1] & days[2];

        int[] list= getBitOffsets(result);
        System.out.println("连续签到列表："+Arrays.toString(list));
        //输出==> 连续签到列表：[10, 13]
    }

上面使用的是long类型来映射用户，实际场景中用户会非常多，如果用户有 20亿，就需要使用单独的服务器来存储。如果服务器能做到高可用，使用 BitSet 也是可以的。但这些数据直接放在内存也是不可取的，可以使用Redis，Redis是一个内存NOSQL数据库，它也支持这种 BitMap的映射。

6.4 权限

用户在系统中的活动往往会有限制，如果系统中所有的权限加起来不超过 64，就也可以使用BitMap的方式来映射。假设有4中权限，伪代码如下：

long permissionCrate= 1L << 0 ;
long permissionUpdate= 1L << 1 ;
long permissionDelete= 1L << 2 ;
long permissionQuery= 1L << 3 ;

某个用户A拥有 permissionCrate， permissionQuery 两种权限,伪代码如下：

long userA_permissions = permissionCrate | permissionQuery ;

现在用户A 登录系统后，要做 permissionDelete 操作，此时就需要鉴权：

if( permissionDelete & userA_permissions == permissionDelete){
    // 可以操作
}else {
    // 没有权限
}

7. 字节数组与 long/int之间的相互转换

java中 long类型占用8个字节，int占用 4 个字节，那么如何将它们转换为字节数组。

为什么有将long转换为字节数组的需求呢？有这样的一个场景：

两个用户之间需要传递文件，用户A 选择了一个文件列表传递给用户B，他们之间使用socket进行通信。我们知道socket通信的时候，我们要操作的主要是比特流（二进制流）。

实现的时候首先要获取 A 文件列表中的一个文件，读取文件的名称，文件的字节数. 接着向socket流写入一个long类型的数据，这个数据表示文件名的长度，然后再将文件名转换为字节数组写入流中，然后再写入一个long类型的数据，这个long类型的数据表示整个文件的长度，最后写入文件的二进制字节，下一个文件再按照这个规则写入流中。

用户B 需要从 socket流中读取字节，他首先要先读取4个字节（long类型数据），就知道了后面文件名要读取的字节数，紧接着按照这个字节数读取流就得到了文件名，接着读取4个字节，这表示文件内容的长度，按照这个长度读取流的内容，这样一个文件就算是传递完成了，接着按照前面的方式读取下一个文件。

在上面的场景中就用到了需要将int， long类型的值以字节数组的方式写入到流中，那么读取解析的时候，又需要将字节数组转换为int或者long。

7.1 long/int 转字节数组

long或者int 拆分成字节数组

long或者int 二进制序列最右边的 8 位(一个字节)，它应该是字节数组的最后一个元素，最左边的8位(一个字节)为数组的第一个元素

那么如何将每8位（1个字节）拆分出来，然后放到字节数组中？

拆分最前面的 00 ，只需要整体无符号右移 7个字节的长度，共56 个二进制位，这样它就会到达最末端，然后与 0xFF 做 & 运算，这样就将这个字节拆出来了。

接着的01 ，只需要整体无符号右移6个字节的长度，共48个二进制位，这样它也到达最末端，然后与0xFF 做 & 运算

其它一次类推即可。

数组组装成long或者int

过程刚好与拆成字节数组相反，对于 00这个字节，需要与 0x00000000000000FFL做与运算（注意最后有一个L，表示long类型），这样就将它提升为long类型，然后左移 7个字节的位置（56位），同理，01这个字节要左移 64位，最终将每个移动后的结果做 | 运算，就将一个long类型的数据组装好了。

注意左移的时候，一定要将类型提升为long类型后，也就是 & 0x00000000000000FFL 运算，再左移 56，要不然，移动的就不是56位，而是 56%32 = 24 位，因为java中 byte类型在参与运算的时候会提升为int类型，而int类型是 32 位，所以移位的时候会做 56%32 的操作，真正移动的是24位，而不是56位，这样最终的结果就会出现错误。

   public byte[] long2Bytes(long value){ //高位在左边，地位在右边
        byte b0=(byte)((value >>> 56) & 0xFF); //无符号右移,左边补0
        byte b1=(byte)((value >>> 48) & 0xFF);
        byte b2=(byte)((value >>> 40) & 0xFF);
        byte b3=(byte)((value >>> 32) & 0xFF);
        byte b4=(byte)((value >>> 24) & 0xFF);
        byte b5=(byte)((value >>> 16) & 0xFF);
        byte b6=(byte)((value >>> 8) & 0xFF);
        byte b7=(byte)(value & 0xFF);
        return new byte[]{b0,b1,b2,b3,b4,b5,b6,b7};

    }
    public long bytes2Long(byte[] bytes){
        long b0=(bytes[0] & 0x00000000000000FFL) << 56;
        long b1=(bytes[1] & 0x00000000000000FFL) << 48;
        long b2=(bytes[2] & 0x00000000000000FFL) << 40;
        long b3=(bytes[3] & 0x00000000000000FFL) << 32;
        long b4=(bytes[4] & 0x00000000000000FFL) << 24;
        long b5=(bytes[5] & 0x00000000000000FFL) << 16;
        long b6=(bytes[6] & 0x00000000000000FFL) << 8;
        long b7=bytes[7] & 0x00000000000000FFL;
        return b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7;
    }
    public byte[]  int2Bytes(int value){
        byte b0=(byte)((value >>> 24) & 0xFF);
        byte b1=(byte)((value >>> 16) & 0xFF);
        byte b2=(byte)((value >>> 8) & 0xFF);
        byte b3=(byte)(value & 0xFF);
        return new byte[]{b0,b1,b2,b3};
    }
    public int  bytes2Int(byte[] bytes){
        int b0=(bytes[0] & 0x000000FF) << 24;
        int b1=(bytes[1] & 0x000000FF) << 16;
        int b2=(bytes[2] & 0x000000FF) << 8;
        int b3=bytes[3] & 0x000000FF;
        return b0 | b1 | b2 | b3;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

编程算法

登录后参与评论

0 条评论

热度