位运算基本操作

  • 按位与 —— &

    只有两个操作数对应的位都是1，结果中的这一位才是1

  • 按位或 —— |

    只有两个操作数对应的位都是0，结果中的这一位才是0

  • 按位异或 —— ^

    两个操作数对应的位不同时取1，相同取0

  • 按位非 —— ~

    将操作数的所有位取反，对于带符号整数，相当于改变符号后减一

  • 左移 —— <<

    用来将一个二进制数各位全部向左移动若干位

  • 带符号右移 —— >>

    用来将一个二进制数各位全部向右移动若干位，如果是正数，最高位补0，负数补1

  • 无符号右移 —— >>>

    用来将一个二进制数各位全部向右移动若干位，最高位补0

位运算技巧

常见位运算变换

功能 位运算 示例
在末尾后添0 101101 -> 1011010 x << 1
在末尾后添1 101101 -> 1011011 (x << 1) + 1
把末位变成1 101100 -> 101101 x | 1
把最后一位变成0 101101 -> 101100 (x | 1) - 1
最后一位取反 101101 -> 101100 x ^ 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 ^ (1 << (k - 1))
取末k位 1101101 -> 1101, k = 5 x & ((1 << k) - 1)
取右数第k位 1101101 -> 1, k = 4 (x >>> (k - 1)) & 1
把末k位变成1 101001 -> 101111, k = 4 x | ((1 << k) - 1)
末k位取反 101001 -> 100110, k = 4 x ^ ((1 << k) - 1)
把右边连续的1变成0 100101111 -> 100100000 x & (x + 1)
把右起第一个0变成1 100101111 -> 100111111 x | (x + 1)
把右边连续的0变成1 11011000 -> 11011111 x | (x - 1)
取右边连续的1 100101111 -> 1111 (x ^ (x + 1)) >>> 1
去掉右起第一个1的左边 100101000 -> 1000 x & (x ^ (x - 1))

  • 任何数和 1 进行&运算，结果不变；任何数和 0 进行|运算，结果不变

  • 任何数和 0 进行&运算，结果为 0；任何数和 1 进行|运算，结果为 1

  • 任何数和 1 进行^运算，相当于取反；任何数和 0 进行^运算，结果不变

其他应用

  • x取反再与x相加，相当于把所有二进制位设为 1，其十进制结果为 -1

    1
    x + (~x) = -1

  • 计算x + 1与x - 1

    1
    -(~x) == x + 1
    1
    ~(-x) == x - 1

  • 取相反数

    即取反并加1

    1
    2
    3
    ~n + 1
    // or
    (n ^ -1) + 1

  • 交换两个数

    1
    2
    3
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;

判断条件

  • 判断一个数为奇数还是偶数

    二进制最后一位决定了这个数的奇偶性，直接按位与 1 就可以判断

    1
    2
    3
    4
    5
    if(n & 1) {
      // n是奇数
    } else {
      //n是偶数
    }

  • 判断两个数符号是否相同

    二进制第一位表示符号，所以符号相同就为0（正数），符号不同就为1（负数）

    1
    2
    3
    4
    5
    if(n ^ m >= 0) {
      //n和m同符号
    } else {
      //n和m不同号
    }