乐趣区

关于java:位运算的奇淫技巧非常有趣

jiezi

根本的位操作符有与、或、异或、取反、左移、右移这 6 种:

位运算示例操作

位运算示例操作

位运算 性能 示例
x >> 1 去掉最初一位 101101->10110
x << 1 在最初加一个 0 101101->1011010
x << 1 在最初加一个 1 101101->1011011
x\ 1 把最初一位变成 1 101100->101101
x & -2 把最初一位变成 0 101101->101100
x ^ 1 最初一位取反 101101->101100
x \ (1 << (k-1)) 把右数第 k 位变成 1 101001->101101,k=3
x & ~ (1 << (k-1)) 把右数第 k 位变成 0 101101->101001,k=3
x ^(1 <<(k-1)) 右数第 k 位取反 101001->101101,k=3
x & 7 取末三位 1101101->101
x & (1 << k-1) 取末 k 位 1101101->1101,k=5
x >> (k-1) & 1 取右数第 k 位 1101101->1,k=4
x \ ((1 << k)-1) 把末 k 位变成 1 101001->101111,k=4
x ^ (1 << k-1) 末 k 位取反 101001->100110,k=4
x & (x+1) 把左边间断的 1 变成 0 100101111->100100000
x \ (x+1) 把右起第一个 0 变成 1 100101111->100111111
x \ (x-1) 把左边间断的 0 变成 1 11011000->11011111
(x ^ (x+1)) >> 1 取左边间断的 1 100101111->1111
x & -x 去掉右起第一个 1 的右边 100101000->1000
x&0x7F 取末 7 位 100101000->101000
x& ~0x7F 是否小于 127 001111111 & ~0x7F->0
x & 1 判断奇偶 00000111&1->1

应用位运算的两点注意事项：

  1. 位操作只能用于整形数据，对 float 和 double 类型进行位操作会被编译器报错。
  2. 位操作符的运算优先级比拟低，因为尽量应用括号来确保运算程序

1. 判断一个数值是不是 2 的整数次方

解题思路：

2 的整数次方对应的二进制的最高位上只有一个 1，如：8，二进制为 1000；4，二进制为 0100，

那么将该数字减去 1 再与该数字进行与运算，减去 1 后失去二进制：7，二进制为 0111；3，二进制为 0011，能够看出 8&7 为 0，

4&3 为 0

所以，如果 n 是 2 的整数次方，那么 n & (n – 1) 后果肯定为 0:

n 的数值要大于 0 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          int n = 8;
    
5.          if ((n & (n-1)) == 0){6.              System.out.println("整数的二次方 true");
    
7.          }else{8.              System.out.println("不是整数的二次方");
    
9.          }
    
10.      }
    
11.  }

2. 应用位运算替换两个数字【不应用两头变量】

应用异或 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          int n = 8, m = 10;
    
5.          n ^= m;
    
6.          m ^= n;
    
7.          n ^= m;
    
8.          System.out.println(n + "," + m);
    
9.      }
    
10.  }

如：a = 13, b = 6:
a 的二进制为 13 = 8 + 4 + 1 = 1101(二进制)
b 的二进制为 6 = 4 + 2 = 110(二进制)

  1. a ^= b a = 1101 ^ 110 = 1011;
  2. b ^= a b = 110 ^ 1011 = 1101; 即 b == 13
  3. a ^= b a = 1011 ^ 1101 = 110; 即 a == 6

其余办法， 应用加减法 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          int n = 8, m = 10;
    
5.          n = n + m;
    
6.          m = n - m;
    
7.          n = n - m;
    
8.          System.out.println(n + "," + m);
    
9.      }
    
10.  }

3. 计算在一个 32 位的整数的二进制示意中有多少个 1

循环应用 x & (x-1) 消去最初一位 1，计算总共消去了多少次即可。

如：

13：1101

12：1100

相与：1100，消去最初一位 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          // 计算在一个 32 位的整数的二进制示意中有多少个 1
    
5.          int m = 13, num = 0;
    
6.          while (true){7.              if (m == 0) break;
    
8.              m &= (m-1);
    
9.              num ++;
    
10.          }
    
11.          System.out.println(num);
    
12.      }
    

14.  }

4. 负数变成正数，或者正数变成负数

变换符号只须要取反后加 1 即可 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          // 计算在一个 32 位的整数的二进制示意中有多少个 1
    
5.          int m = -13;
    
6.          int changeM = ~m + 1;
    
7.          System.out.println(changeM);
    
8.      }
    

10.  }

5. 判断一个数值的奇偶

只有依据最未位是 0 还是 1 来决定，为 0 就是偶数，为 1 就是奇数，所以只须要与 1 相与。

因而能够用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断 a 是不是偶数。



1.  public class Main {3.      public static void main(String[] args) {
    
4.          int m = -14;
    

6.          if ((m & 1) == 1){7.              System.out.println("ji");
    
8.          }else{9.              System.out.println("ou");
    
10.          }
    
11.      }
    

13.  }

6. 乘以 2 的 m 次方操作

乘以 2 的操作，即 2 的 1 次方，左移 1 位 

System.out.println(10<<1);

 推导扩大：

乘以 2 的 m 次方 

System.out.println(10<<2); // 乘以 2 的 2 次方，相当于乘以 4

7. 除以 2 运算 (负奇数的运算不可用)

System.out.println(10>>1);

8. 转换成绝对值 



1.  public class Main {3.      public static void main(String[] args) {
    
4.          int n = 12;
    

6.          System.out.println(0 >> 31); // 0
    
7.          System.out.println(10 >> 31);  // 0
    
8.          System.out.println(-10 >> 31);  // -1
    

10.          System.out.println((n ^ (n >> 31)) - (n >> 31));  // 12 
    

12.      }
    

14.  }
  1. 首先：n>>31 获得 n 的符号

若 n 为负数，n>>31 等于 0；若 n 为正数，n>>31 等于 -1 若 n 为负数 n^0- 0 数不变；

  1. 若 n 为正数 n^-1 须要计算 n 和 -1 的补码，异或后再取补码，后果 n 变号并且绝对值减 1，再减去 - 1 就是绝对值

9. 判断两数符号是否雷同

true 示意 x 和 y 有雷同的符号，false 示意 x，y 有相同的符号。

System.out.println((a ^ b) > 0);

10. 求两个整数（int）的平均数 

System.out.println((a+b) >> 1);

11. 求两个整数的最大值 



1.  int max(int a,int b){2.      return b & ((a-b) >> 31) | a & (~(a-b) >> 31);
    
3.      /* 如果 a >=b,(a-b)>>31 为 0，否则为 -1*/
    
4.  }

12. 求两个整数的最小值 



1.  int min(int a,int b){2.      return a & ((a-b) >> 31) | b & (~(a-b) >> 31);
    
3.      /* 如果 a >=b,(a-b)>>31 为 0，否则为 -1*/
    
4.  }

13.  两个整数的加法运算

应用 ^ 和 & 将两个整数相加

  1. 两个数异或：相当于两个数相加，而不思考进位；
  2. 两个数相与，并左移一位：相当于求得进位；

13+11 =？;

13 的二进制      1 1 0 1                     —–a        13

11 的二进制      1 0 1 1                     —–b        11  

 (a&b) <<1  ->   1 0 0 1 0                         —–d         18

          a^b  ->     0 1 1 0                   —–e          6

 (d&e) <<1  ->   0 0 1 0 0                       ——f         4

          d^e  ->  1 0 1 0 0                  —–g        20

 (f&g) <<1  ->   0 1 0 0 0                       ——h        8

          f^g  ->  1 0 0 0 0                   ——i           16

 (h&i) <<1  ->   0 0 0 0 0                      ——h        0       —- ——– 没有进位了，则退出循环

          h^i  ->  1 1 0 0 0                  ——i           24



1.  private static int getSum(int a, int b) {2.      if (a == 0) return b;
    
3.      if (b == 0) return a;
    
4.      while (b != 0) {
    
5.          int carry = a & b; // 失去有进位的地位
    
6.          a = a ^ b; // 间接相加，然而没有进位
    
7.          b = carry << 1; // 失去进位
    
8.      }
    
9.      return a;
    
10.  }

我的项目举荐：

2000 多 G 的计算机各行业电子资源分享（继续更新）

2020 年微信小程序全栈我的项目之喵喵交友【附课件和源码】

Spring Boot 开发小而美的集体博客【附课件和源码】

Java 微服务实战 296 集大型视频 - 谷粒商城【附代码和课件】

Java 开发微服务畅购商城实战【全 357 集大我的项目】- 附代码和课件

最全最具体数据结构与算法视频 -【附课件和源码】​​​​​​​

退出移动版