[toc]
基本原理
0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = xx ^ 1s = ~x x & 1s = x x | 1s = 1sx ^ x = 0 x & x = x x | x = x
利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
1^1^2 = 2
利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
01011011 &
00111100
--------
00011000
利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。
01011011 |
00111100
--------
01111111
位与运算技巧
n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。
01011011 &
01011010
--------
01011010
n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
10110100 &
01001100
--------
00000100
n-(n&(-n)) 则可以去除 n 的位级表示中最低的那一位 1，和 n&(n-1) 效果一样。
移位运算
n 为算术右移，相当于除以 2n，例如 -7 >> 2 = -2。
11111111111111111111111111111001 >> 2
--------
11111111111111111111111111111110
n 为无符号右移，左边会补上 0。例如 -7 >>> 2 = 1073741822。
11111111111111111111111111111001 >>> 2
--------
00111111111111111111111111111111
<< n 为算术左移，相当于乘以 2n。-7 << 2 = -28。
11111111111111111111111111111001 << 2
--------
11111111111111111111111111100100
mask 计算
要获取 11111111，将 0 取反即可，~0。
要得到只有第 i 位为 1 的 mask，将 1 向左移动 i-1 位即可，1<<(i-1) 。例如 1<<4 得到只有第 5 位为 1 的 mask ：00010000。
要得到 1 到 i 位为 1 的 mask，(1<<i)-1 即可，例如将 (1<<4)-1 = 00010000-1 = 00001111。
要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~((1<
static int Integer.bitCount(); // 统计 1 的数量
static int Integer.highestOneBit(); // 获得最高位
static String toBinaryString(int i); // 转换为二进制表示的字符串
剑指 Offer 15. 二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
解法
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
sum++;
// n & (n - 1)运算，将n的二进制数最后一位1变为0，循环直到n为0
n = n & (n - 1);
}
return sum;
}
}
汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
解法
使用 z&(z-1) 去除 z 位级表示最低的那一位。
class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y;
int count = 0;
while (z != 0) {
z &= (z - 1);
count++;
}
return count;
}
}
剑指 Offer 65. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数
位运算
class Solution {
public int add(int a, int b) {
// 当进位为 0 时跳出
while (b != 0) {
// c = 进位
int c = (a & b) << 1;
// a 为非进位和
a ^= b;
// b 为进位
b = c;
}
return a;
}
}
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解法
两个相同的数做异或操作等于0，0与任何数异或，数值不变。
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
// 两个相同的数做异或操作等于0，0与任何数异或，数值不变。
result = result ^ num;
}
return result;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
位运算
异或满足交换律，第一步异或，相同的数其实都抵消了，剩下两个不同的数。这两个数异或结果肯定有某一位为1，不然都是0的话就是相同数。找到这个位，不同的两个数一个在此位为0，另一个为1。按此位将所有数分成两组，分开后各自异或，相同的两个数异或肯定为0（而且分开的时候，两个数必为一组）。剩下的每组里就是我门要找的数。
class Solution {
public int[] singleNumbers(int[] nums) {
// 用于将所有的数异或起来
int k = 0;
for (int num : nums) {
k ^= num;
}
// 获得k中最低位的1
int mask = 1;
while ((k & mask) == 0) {
mask <<= 1;
}
// first、second为两个不同的数
int first = 0;
int second = 0;
// first、second中有一个数的二进制形式最后一个1和mask相同，所有可以将这两个数分开
for (int num : nums) {
if ((num & mask) == 0) {
first ^= num;
} else {
second ^= num;
}
}
return new int[]{first, second};
}
}
剑指 Offer 56 - II. 数组中数字出现的次数 II
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
位运算
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;
上述思路同样适用于数组中一个数字出现一次，其他数字出现奇数次问题(如果是偶数次，直接用异或就可)。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
int[] bitSum = new int[32];
int res = 0;
for (int num : nums) {
int bitMask = 1;
for (int i = 31; i >= 0; i--) {
if ((num & bitMask) != 0) {
bitSum[i]++;
}
bitMask = bitMask << 1;
}
}
for (int i = 0; i < 32; i++) {
res = res << 1;
res += bitSum[i] % 3;
}
return res;
}
}
缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
解法
class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result = result ^ i ^ nums[i];
}
return result ^ nums.length;
}
}
颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
解法
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int ans = 0;
for (int bitsize = 31; n != 0; n = n >>> 1, bitsize--) {
ans += (n & 1) << bitsize;
}
return ans;
}
}
不用额外变量交换两个整数
两个相同的数做异或操作等于0，0与任何数异或，数值不变。
a = a ^ b;
b = a ^ b;
a = a ^ b;
2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 2^0 = 1
示例 2:
输入: 16
输出: true
解释: 2^4 = 16
示例 3:
输入: 218
输出: false
解法
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
4的幂
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
示例 1:
输入: 16
输出: true
示例 2:
输入: 5
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
解法
这种数在二进制表示中有且只有一个奇数位为 1，例如 16（10000）。
class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
}
}
交替位二进制数
给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1:
输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:
输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:
输入: 11
输出: False
解释:
11的二进制数是: 1011
示例 4:
输入: 10
输出: True
解释:
10的二进制数是: 1010
解法
对于 1010 这种位级表示的数，把它向右移动 1 位得到 101，这两个数每个位都不同，因此异或得到的结果为 1111。
class Solution {
public boolean hasAlternatingBits(int n) {
int a = (n ^ (n >> 1));
return (a & (a + 1)) == 0;
}
}
数字的补数
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
示例 1:
输入: 5
输出: 2
解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2:
输入: 1
输出: 0
解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
注意:
给定的整数保证在 32 位带符号整数的范围内。
你可以假定二进制数不包含前导零位。
本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同
解法
对于 00000101，要求补码可以将它与 00000111 进行异或操作。那么问题就转换为求掩码 00000111。
class Solution {
public int findComplement(int num) {
if (num == 0) {
return 1;
}
int mask = 1 << 30;
while ((num & mask) == 0) {
mask >>= 1;
}
mask = (mask << 1) - 1;
return num ^ mask;
}
}
两整数之和
不使用运算符 + 和 - ，计算两整数 a 、b之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
解法
a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。
递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。
class Solution {
public int getSum(int a, int b) {
return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
}
}
最大单词长度乘积
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
解法
本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的整数来存储每个字符是否出现过。
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] val = new int[n];
for (int i = 0; i < n; ++i) {
for (char c : words[i].toCharArray()) {
val[i] |= 1 << (c - 'a');
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((val[i] & val[j]) == 0) {
ret = Math.max(ret, words[i].length() * words[j].length());
}
}
}
return ret;
}
}
比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
进阶:
给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
解法
对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;
class Solution {
public int[] countBits(int num) {
int[] dp = new int[num + 1];
for (int i = 1; i <= num; i++) {
dp[i] = dp[i & (i - 1)] + 1;
}
return dp;
}
}
若有收获，就点个赞吧
0 人点赞
