Bit Related Operations
Sum of Two Integers
把xor操作看成求和操作，把&操作看成求仅为进位操作，当进位为0时，我们就返回和。
public class Solution {
public int getSum(int a, int b) {
if (b == 0) {
return a;
}
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}
}
Bitwise AND of Numbers Range
当m ！= n时，至少有一个奇数一个偶数，那他们&以后，最后一位一定是0。我们就不断的right shift两个数，知道两个数相等，然后左移之前走过的位数就是答案。
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int move = 0;
while (m != n) {
m = m >> 1;
n = n >> 1;
move++;
}
return m << move;
}
}
UTF-8 Validation
这题把题意读懂以后，就是一道前向型的双指针问题。
public class Solution {
public boolean validUtf8(int[] data) {
if (data == null || data.length == 0) {
return true;
}
int i = 0;
while (i < data.length) {
int count = 0;
int bit = 7;
while (bit >= 0 && (data[i] >> bit & 1) == 1) {
bit--;
count++;
}
if (count == 1 || count > 4) {
return false;
}
if (count == 0) {
i++;
} else {
count--;
i++;
if (i + count > data.length) {
return false;
}
for (int j = i; j < i + count; j++) {
if ((data[j] >> 7 & 1) != 1) {
return false;
}
if ((data[j] >> 6 & 1) != 0) {
return false;
}
}
i += count;
}
}
return true;
}
}
Number Complement
先找到最高位是1的那一位，然后逐位构造最后的结果。
public class Solution {
public int findComplement(int num) {
int bit = 30;
while (bit >= 0) {
if ((num >> bit & 1) == 0) {
bit--;
} else {
break;
}
}
int answer = 0;
for (int i = 0; i <= bit; i++) {
if ((num >> i & 1) == 0) {
answer |= 1 << i;
}
}
return answer;
}
}
Integer Replacement
public class Solution {
public int integerReplacement(int n) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(1, 0);
map.put(2, 1);
return helper(map, n);
}
private int helper(Map<Integer, Integer> map, int n) {
if (map.containsKey(n)) {
return map.get(n);
}
int steps = -1;
if (n % 2 == 0) {
steps = helper(map, n / 2) + 1;
} else {
steps = Math.min(helper(map, n - 1) + 1, helper(map, 1 + (n - 1) / 2) + 2);
}
map.put(n, steps);
return steps;
}
}
解法二：
public class Solution {
public int integerReplacement(int n) {
if (n <= 1) {
return 0;
}
int count = 0;
while (n != 1) {
if ((n & 1) == 0) {
n = n >>> 1;
} else {
if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
n--;
} else {
n++;
}
}
count++;
}
return count;
}
}
Convert a Number to Hexadecimal
从最低位向最高位，4位4位的构造。
public class Solution {
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
public String toHex(int num) {
if (num == 0) {
return "0";
}
String result = "";
while (num != 0) {
result = map[(num & 15)] + result;
num = num >>> 4;
}
return result;
}
}
Maximum XOR of Two Numbers in an Array
先构造一个trie，然后每一个num依次和trie里的node比较，得到能构成最大值的candidate。
public class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
Trie root = new Trie();
for (int num: nums) {
Trie node = root;
for (int i = 31; i >= 0; i--) {
int bit = num >>> i & 1;
if (node.children[bit] == null) {
node.children[bit] = new Trie();
}
node = node.children[bit];
}
}
int result = Integer.MIN_VALUE;
for (int num: nums) {
Trie node = root;
int temp = 0;
for (int i = 31; i >= 0; i--) {
int bit = num >>> i & 1;
if (node.children[bit ^ 1] != null) {
temp |= 1 << i;
node = node.children[bit ^ 1];
} else {
node = node.children[bit];
}
}
result = Math.max(result, temp);
}
return result;
}
}
class Trie {
Trie[] children;
public Trie() {
children = new Trie[2];
}
}
Binary Watch
DFS
public class Solution {
public List<String> readBinaryWatch(int num) {
List<String> result = new ArrayList<String>();
if (num < 0 || num > 10) {
return result;
}
for (int i = 0; i <= num && i <= 4; i++) {
int j = num - i;
if (j < 0 || j > 6) {
continue;
}
List<Integer> hours = helper(i, true);
List<Integer> minutes = helper(j, false);
for (int h: hours) {
for (int m: minutes) {
String s = h + ":" + (m < 10 ? "0" : "") + m;
result.add(s);
}
}
}
return result;
}
private List<Integer> helper(int n, boolean getHour) {
List<Integer> result = new ArrayList<Integer>();
int count = getHour ? 4 : 6;
dfs(result, n, count, 0, 0);
return result;
}
private void dfs(List<Integer> result, int n, int count, int current, int pos) {
if (n == 0) {
if (count == 4 && current >= 12 || count == 6 && current >= 60) return;
result.add(current);
return;
}
for (int i = pos; i < count; i++) {
current |= 1 << i;
dfs(result, n - 1, count, current, i + 1);
current -= 1 << i;
}
}
}