位运算技巧

好用的位操作

  1. class Solutions {
  2.     void fun() {
  3.         // 利用或操作 空格和英文字符转化小写
  4.         ('a' | ' ') = 'a';
  5.         ('A' | ' ') = 'a';
  7.         // 利用与操作 _下划线和英文字符转化大写
  8.         ('a' & '_') = 'A';
  9.         ('A' & '_') = 'A';
  10.         // 利用异或操作 空格和英文字符大小写互换
  11.         ('a' ^ ' ') = 'A';
  12.         ('A' ^ ' ') = 'a';
  14.         // 判断两个数是否异号
  15.         int x = -1, y = 2;
  16.         boolean f = ((x ^ y) < 0); // true
  17.         x = 1;
  18.         y = 2;
  19.         boolean f = ((x ^ y) < 0); // false
  21.         // 不需要临时变量可交换两数
  22.         int a = 1, b = 2;
  23.         a ^= b;
  24.         b ^= a;
  25.         a ^= b;
  27.         // 加1
  28.         int n = 1;
  29.         n = -~n;
  31.         // 减1
  32.         int m = 2;
  33.         m = ~-m;
  34.     }
  36.     void bitOperate() {
  37.         int n = 234;
  38.         // 消除数字n最后一个1，n转换成二进制后最后一个数字1
  39.         n & n - 1;
  40.     }
  41. }

【应用示例】

  1. class Example {
  3.     /**
  4.      * 136
  5.      * https://leetcode-cn.com/problems/single-number/
  6.      * 计算数组里只出现一次的数组
  7.      * 一个数字异或它本身 = 0
  8.      * 一个数字异或0 = 它本身
  9.      *
  10.      * @param nums
  11.      * @return
  12.      */
  13.     public int singleNumber(int[] nums) {
  14.         int vis = 0;
  15.         for (int i = 0; i < nums.length; i++) {
  16.             vis ^= nums[i];
  17.         }
  18.         return vis;
  19.     }
  21.     /**
  22.      * 231
  23.      * https://leetcode-cn.com/problems/power-of-two/
  24.      * 判断数字n是否是2的幂次方
  25.      * n & n - 1
  26.      * 数字与数字-1，消除最后一个1
  27.      * 如果是幂次方，则只有一个1
  28.      * @param n
  29.      * @return
  30.      */
  31.     public boolean isPowerOfTwo(int n) {
  32.         if (n <= 0) {
  33.             return false;
  34.         }
  35.         return (n & n - 1) == 0;
  36.     }
  38.     /**
  39.      * 191
  40.      * https://leetcode-cn.com/problems/number-of-1-bits/submissions/
  41.      * 计算汉明权重，算出有多少位=1
  42.      * n & n - 1
  43.      * 数字与数字-1，消除最后一个1
  44.      * 一直到数字没有1即 = 0
  45.      * @param n
  46.      * @return
  47.      */
  48.     public int hammingWeight(int n) {
  49.         int res = 0;
  50.         while (n != 0) {
  51.             n &= n - 1;
  52.             res++;
  53.         }
  54.         return res;
  55.     }
  56. }