位运算符

& :与
| :或
^ :异或
~ :非(取反)
>> << :右移(补符号位),左移(补0)
>>> :右移(0补充高位)
对于int型,1<<35与1<<3是相同的,而左边的操作数是long型时需要对右侧操作数模64

image

异或:
可以理解为不进位加法:1+1=0,0+0=0,1+0=1
性质:
1、交换律:a ^ b = b ^ a
2、结合律:(a ^ b) ^ c = a ^ (b ^ c)
3、对于任何数x,都有x ^ x = 0,x ^ 0 = x
4、自反性:a ^ b ^ b = a ^ 0 = a,连续和同一个因子做异或运算,最终结果为自己

应用

判断奇偶数

x & 1 = 1 x是奇数
x & 1 = 0 x是偶数

核心是判断二进制数最后一位是1还是0

交换两个整数变量的值

使用前提:a,b不相等

a = a^b;
b = a^b;
a = a^b;

不用判断语句求整数绝对值

(num^(num>>31))+(num>>>31)

11111111 11111111 11111111 11110111:num
11111111 11111111 11111111 11111111:num>>31
00000000 00000000 00000000 00001000:num^(num>>31)
00000000 00000000 00000000 00000001:num>>>31
00000000 00000000 00000000 00001001:num^(num>>31))+(num>>>31

正数显然满足
负数的相反数是原码含符号位取反加一

消除最低位的1

x&(x-1) :可以使二进制数x的最低位的1变成0;

例题

找出唯一成对的数

1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

核心:x^x=0

可以强行配凑消去其他元素:这1001个元素连续异或,再异或上1-1000这1000个数。
其他元素都出现2次,异或后变成0.而唯一的一个元素值出现3次,连续异或后值不变。

public static void main(String[] args) {
        int []arr = new int[]{1,2,3,4,4,5};
        int ans = 0;
        for(int i=1;i<=5;i++){
            ans^=i;
        }
        for(int i=0;i<6;i++){
            ans^=arr[i];
        }
        System.out.println(ans);
}

找出落单的数

一个数组里除了某一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

public static void main(String[] args) {
        int []arr = new int[]{1,1,3,4,4};
        int ans = 0;
        for(int i=0;i<arr.length;i++){
            ans^=arr[i];
        }
        System.out.println(ans);
}

二进制中1的个数

请实现一个函数,输入一个整数,输出该整数二进制表示中1的个数。
例:9的二进制表示为1001,有2位是1

法一:
该二进制数不断无符号右移并与1做与运算,结果为1则count++,直到该数变为0

public static void main(String[] args) {
        int n=-1;
        int count = 0;
        while (n!=0){
            int tmp = n&1;
            if(tmp == 1) count++;
            n = n >>> 1 ;
        }
        System.out.println(count);
    }   //32

法二:
每次使该二进制数的一个为1的二进制位变成0,count++,直到该数变成0;
x&(x-1) :可以使二进制数的最低位的1变成0;

public static void main(String[] args) {
        int n=-1;
        int count = 0;
        while (n!=0){
            n = n&(n-1);
            count++;
        }
        System.out.println(count);
    }

是不是2的整数次方

用一条语句判断一个整数是不是2的整数次方

也就是一个整数的二进制形式中为1的二进制位是不是只有一个。联系上一题,也就是count是不是为1

public static void main(String[] args) {
        int n=65536;
        System.out.println((n&(n-1))==0);
}

整数的二进制奇偶位交换

先取出偶数位和奇数位,偶数结果右移一位,奇数结果左移一位,最后异或
abababab abababab abababab abababab
a0a0a0a0 a0a0a0a0 a0a0a0a0 a0a0a0a0(ou)
0b0b0b0b 0b0b0b0b 0b0b0b0b 0b0b0b0b(ji)
0a0a0a0a 0a0a0a0a 0a0a0a0a 0a0a0a0a(ou>>>1)
b0b0b0b0 b0b0b0b0 b0b0b0b0 b0b0b0b0(ji<<1)
babababa babababa babababa babababa

public static void main(String[] args) {
    int a = 0b01000000_00000000_00000000_00000000;
    System.out.println(a);
    int b = m(a);
    System.out.println(b);  //0b10000000_00000000_00000000_00000000
  }

  private static int m(int i) {
    int ou = i & 0xaaaaaaaa;//和1010 1010 1010 。。。。做与运算取出偶数位
    int ji = i & 0x55555555;//和0101 0101 0101 。。。。做与运算取出奇数位
    return (ou >>> 1) ^ (ji << 1); // 连起来
  }

0~1直接的浮点实数的二进制表示

给定一个介于0和1之间的实数,(如0.625),类型为double,打印它的二进制表示(0.101,因为小数点后的二进制分别表示0.5,0.25.0.125……) 。
如果该数字无法精确地用32位以内的二进制表示,则打印“ERROR”

public static void main(String[] args) {
    double num = 0.625;
    StringBuilder sb = new StringBuilder("0.");
    while (num > 0) {
      //乘2:挪整
      double r = num * 2;
      //判断整数部分
      if (r >= 1) {
        sb.append("1");
        //消掉整数部分
        num = r - 1;
      } else {
        sb.append("0");
        num = r;
      }

      if (sb.length() > 34) {
        System.out.println("ERROR");
        return;
      }

    }
    System.out.println(sb.toString());
  }

出现k次与出现1次

数组中只有一个数出现了1次,其他的数都出现了k次,请输出只出现了1次的数。

2个相同的2进制数做不进位加法,结果为0
10个相同的10进制数做不进位加法,结果为O
k个相同的k进制数做不进位加法,结果为0

public static void main(String[] args) {
    int[] arr = {2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6, 0, 0, 0};
    int len = arr.length;
    char[][] kRadix = new char[len][];
    int k = 3;

    int maxLen = 0;
    //转成k进制字符数组
    //对于每个数字
    for (int i = 0; i < len; i++) {
      //求每个数字的k进制字符串并翻转,然后转为字符数组
      kRadix[i] = new StringBuilder(Integer.toString(arr[i], k)).reverse().toString().toCharArray();
      if (kRadix[i].length > maxLen)
        maxLen = kRadix[i].length;
    }
    //不进位加法
    int[] resArr = new int[maxLen];
    for (int i = 0; i < len; i++) {
      //  不进位加法
      for (int j = 0; j < maxLen; j++) {
        if (j >= kRadix[i].length)
          resArr[j] += 0;
        else
          resArr[j] += (kRadix[i][j] - \'0\');
      }
    }

    int res = 0;
    for (int i = 0; i < maxLen; i++) {
      res += (resArr[i] % k) * (int) (Math.pow(k, i));// 8%3=2,
    }
    System.out.println(res);
  }

版权声明:本文为gonghr原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/gonghr/p/15090464.html