Bit Manipulation
消去二进制中最右侧的那个“1”
二进制中最右侧的那个“1”x & (x - 1) // 消去 x 最后一位的 1，比如 x = 12，那么在二进制下就是 (1100)2
x = 1100
x - 1 = 1011
x & (x - 1) = 1000LintCode: 142. O(1) Check Power of 2
Using
O(1)time to check whether an integernis a power of2.
满足要求的N有两个条件：
N > 0
N 的二进制表示有且只有一个
1
所以用“技巧一”可以写出如下Java代码
public class Solution {
/**
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
// write your code here
return (n > 0) && ((n & (n - 1)) == 0);
}
}LintCode: 365. Count 1 in Binary
Count how many
1in binary representation of a 32-bit integer.
上一道题目的变体咯，既然要看有多少个1，那我就一直算下去，直到它变成0
public class Solution {
/*
* @param num: An integer
* @return: An integer
*/
public int countOnes(int num) {
// write your code here
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
};LintCode: 181. Flip Bits
Determine the number of bits required to flip if you want to convert integer
nto integerm.
Solution 1
public class Solution {
/**
* @param a: An integer
* @param b: An integer
* @return: An integer
*/
public int bitSwapRequired(int a, int b) {
// write your code here
String bit = Integer.toBinaryString(a ^ b);
int num = 0;
for (int i = 0; i < bit.length(); i++) {
num += (bit.charAt(i) - '0');
}
return num;
}
}Solution 2
class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public int countOnes(int num) {
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
public int bitSwapRequired(int a, int b) {
// write your code here
return countOnes(a ^ b);
}
};Solution 3
/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/
class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public static int bitSwapRequired(int a, int b) {
// write your code here
int count = 0;
for (int c = a ^ b; c != 0; c = c >>> 1) {
count += c & 1;
}
return count;
}
};巧用异或XOR运算
异或XOR运算a ^ b ^ b = a // 对一个数异或两次等价于没有任何操作LintCode: 82. Single Number
Given
2*n + 1numbers, every numbers occurs twice except one, find it.
XOR Operator
XOR OperatorO(n)TimeO(1)Space
public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
// write your code here
int result = 0, n = A.length;
for (int i = 0; i < n; i++) {
result ^= A[i];
}
return result;
}
}Python collections.Counter()
collections.Counter()O(n)Time at leastO(n)Space
class Solution:
"""
@param A: An integer array
@return: An integer
"""
def singleNumber(self, A):
# write your code here
dict = collections.Counter(A)
for key in dict:
if dict[key] == 1:
return key将两个数不同的位设置为“1”，其余为“0”
int bitFlag = (AXORB & (~ (AXORB - 1)));这一行代码的作用是：找到数字
A和数字B中不相同的一位，并将该位设置为1，其他位设置为0；根据 XOR 的定义，我们知道，在 AXORB 中，为 1 的位即 A 和 B 不相同的位，AXORB 中为 0 的位即 A 和 B 中相同的位所以，要找到A和B中不相同的位，只需要找到在AXORB中从右往左第一个为1的位，保留该位并将其他位置为0即可。
public class Solution {
public int[] singleNumber(int[] nums) {
int AXORB = 0;
for (int num : nums) {
AXORB ^= num;
}
// pick one bit as flag
int bitFlag = (AXORB & (~ (AXORB - 1)));
int[] res = new int[2];
for (int num : nums) {
if ((num & bitFlag) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
}假设数组中两个不同的数字为 A 和 B；
通过遍历整个数组并求整个数组所有数字之间的 XOR，根据 XOR 的特性可以得到最终的结果为
AXORB = A XOR B；通过某种特定的方式，我们可以通过 AXORB 得到在数字 A 和数字 B 的二进制下某一位不相同的位；因为A 和 B 是不相同的，所以他们的二进制数字有且至少有一位是不相同的。我们将这一位设置为 1，并将所有的其他位设置为 0，我们假设我们得到的这个数字为
bitFlag；那么现在，我们很容易知道，数字 A 和 数字 B 中
必然有一个数字与上 bitFlag 为 0；因为bitFlag标志了数字 A 和数字 B 中的某一位不同，那么在数字 A 和 B 中的这一位必然是一个为 0，另一个为 1；而我们在 bitFlag 中将其他位都设置为 0，那么该位为 0 的数字与上 bitFlag 就等于 0，而该位为 1 的数字与上 bitFlag 就等于 bitFlag现在问题就简单了，我们只需要在循环一次数组，将与上
bitFlag为 0 的数字进行XOR运算，与上bitFlag不为 0 的数组进行独立的 XOR 运算。那么最后我们得到的这两个数字就是A和B。
Last updated