algorithm-bit

Bit Manipulation

如何清除从右侧数索引 i 到索引 j 位的值 (based 0):

例如清除 11111111 索引 2 到 索引 4 的值: 变成 11100011

1
2
3
4
int allOnew = ~0; // equal sequence of all 1s
int left = allOnes << (j + 1); // 11111111 左移 5 位 11100000
int right = ((1 << i) - 1); // 00000001 左移 2 位 00000100,减 1: 00000011
int mask = left | right; // 11100011

determine the number of bits you would need to flip to convert interger A to integer B

1
2
Input: 29 (or: 11101), 15 (or: 01111)
Output: 2
  • how you world figure out which bits in two numbers are different. Simple: with an XOR:
1
2
3
4
1 1 1 0 1
0 1 1 1 1
----------
1 0 0 1 0

To check the number of bits that are different between A and B, we simple need to count the number of bits in A^B that are 1.

1
2
3
4
5
6
7
int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a ^ b; c != 0; c = c >> 1) {
count += c & 1;
}
return count;
}

This code is good, but we can make it a bit better. Rather than simply shifting c repeatedly while checking the least significant bit, we can continuously flip the least significant bit and count how long it takes c to reach 0.The operation c = c & ( c - 1) will clear the least significant bit in c.

1
2
3
4
5
6
7
1 0 0 1 0
1 0 0 0 1
----------
1 0 0 0 0 <- 清楚掉最右侧的 1
0 1 1 1 1
----------
0 0 0 0 0 <- 清楚掉最右侧的 1
1
2
3
4
5
6
7
int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a ^ b; c != 0; c = c & (c - 1)) {
count++;
}
return count;
}

Maximum Product of Word Lengths

the two words do not share common letters:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0)
return 0;

int len = words.length;
int[] value = new int[len];

// 标记每个单词所拥有的字母
for (int i = 0; i < len; i++) {
String tmp = words[i];
value[i] = 0;
for (int j = 0; j < tmp.length(); j++) {
// 1 << 0 => 0001
// 1 << 1 => 0010
// 1 << 2 => 0100
// 1 << 3 => 1000
// ...
value[i] |= 1 << (tmp.charAt(j) - 'a');
}
}

int maxProduct = 0;
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++) {
// do not share common letters
if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
maxProduct = words[i].length() * words[j].length();
}

return maxProduct;
}
}

Java Int -> Bit’s String

1
Integer.toBinaryString(int i)

无符右移和有符右移:

1
2
3
4
5
6
7
8
9
// 00111111111111111111111111111110
-5 >>> 2
// 11111111111111111111111111111110
-5 >> 2

// 10
5 >> 1
// 10
5 >>> 1

没有 <<< 这个符号


如何根据 5 (0000 0101) 创建一个 1111 1000:

1
2
3
4
int mask = ~0; // 1111 1111
while ((num & mask) != 0) {
mask <<= 1; // bit left shift 1
}

过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1111 1111 <- Initial Mask
0000 0101
---------
0000 0101

1111 1110 <- Mask Left Shift 1
0000 0101
---------
0000 0100

1111 1100 <- Mask Left Shift 2
0000 0101
---------
0000 0100

1111 1000 <- Mask Left Shift 3
0000 0101
---------
0000 0000

1111 1000 <- Finally, You Got It

476. Number Complement

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int findComplement(int num) {
// num: 5: 0000 0101
unsigned mask = ~0; // 1111 1111
while (num & mask) mask <<= 1; // mask: 1111 1000
// ~mask: 0000 0111
// ~num: 1111 1010
// ----------------
// 0000 0010
return ~mask & ~num;
}
};

推荐文章