Question

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Solution

异或运算相当于不进位的加和。
和运算相当于掩码操作。
或运算相当于保留该位上的1。

由于我们要对所有数字进行异或运算，因此只要能改变某一位对应的数字，我们就可以确保这一位在进行异或运算时结果可以为1。（当不改变时改为的异或运算结果为0，则我们只需要改变改为即可得到1）

将所有我们可以操作的位置变为1，就可以得到最大值。

因此，我们只需要确定哪些位是我们可以操作的即可：

• nums[i]与任意正整数进行异或运算可以得到任意整数。在这个条件下我们可以得到任意的32位整数。
• 然而和运算相当于掩码操作，如果nums[i]对应二进制的某一位上位0，则我们无法通过和运算将这一位改变为1。

只要该位出现过1，则我们可以控制这个位。因此我们可以通过或运算所有数字，保留所有可控制的位。

Code

1
2
3
4
5
6
7
8
9

class Solution {
    public int maximumXOR(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum |= num;
        }
        return sum;
    }
}

Question

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Solution

位运算+哈希表，用整数num记录二进制编码并加入哈希表中。
首先将字符串内的前k位二进制码转换为整数。并将其数值添加到哈希表内。

滑动窗口遍历，维持num为k长度内二进制码所对应的整数，并在遍历时将num加入哈希集合。
如果哈希集合的size达到k长度对应的可组合数，则返回true，否则返回false。

位运算与掩码

为了维护整数num，首先将其二进制编码向左移动一位。
然后与mask进行按位与运算，屏蔽掉多余的位数。

mask的值为k长度对应的可组合数-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean hasAllCodes(String s, int k) {
        if(s.length() < k) return false;    //字符串长度不足则返回false
        char[] bin = s.toCharArray();
        int n = s.length(), m = (int) Math.pow(2, k);
        HashSet<Integer> set = new HashSet<>(); //哈希表记录访问过的数字
        
        int num = Integer.parseInt(s.substring(0,k), 2);    //字符串以二进制转换为整数
        int mask = m-1; //掩码等于寻找长度-1
        set.add(num);
        
        for(int i = k; i < s.length(); i++){  //位运算，维护窗口内整数的值
            num <<= 1;  //位运算左移一位
            num &= mask;    //出界的位置被掩码遮盖
            if(bin[i] == '1') num++;
            set.add(num);
            if(set.size() == m) return true;    //如果哈希表长度等于2^k，则已经遍历了所有组合，返回true
        }
        return false;
    }
}

Question

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Solution

正常的思路可能是用哈希表保存字符串中出现过的字符。此时表的大小是26也是一个常数。

我们可以采用位运算进行状态压缩，通过一个整数的二进制位保存二十六个字符的存在状态。

状态压缩

我们采用一个整数数组bin[]储存状态压缩后的整数。

遍历每个字符串，在字符串中遍历每一个字符。
初始化整数bit为0。在遍历字符时计算当前字符与字符’a’距离的差n，然后将1左移n位，填入（或运算）整数bit中。

比较

遍历words[]中的两个字符串，当bin[i]与bin[j]进行与运算结果为0时，则两个字符串没有共同字符。
此时更新二者长度乘积的最大值max。

最后返回max即可。

时间复杂度：O(L + n2)。L为所有字符的总长度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int maxProduct(String[] words) {
        
        int max = 0;
        int bin[] = new int[words.length];
        
        for(int i = 0; i < words.length; i++){
            int bit = 0;
            for(int j = 0; j < words[i].length(); j++){
                bit |= (1 << (words[i].charAt(j) - 'a'));
            }
            bin[i] = bit;
        }
        
        for(int i = 0; i < words.length; i++){
            for(int j = i+1; j < words.length; j++){
                if((bin[i] & bin[j]) == 0) max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }
}

Question

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Solution

循环，当num不等于零时，如果为奇数则减一，如果为偶数则除以2。
每次循环记录次数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int numberOfSteps(int num) {
        int count =0;
        while(num != 0){
            count++;
            if((num & 1) == 0){
                num/=2;
            }
            else{
                num--;
            }
        }
        return count;
    }
}

Problem

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.

• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return *the size of the largest combination of candidates with a bitwise AND greater than *0.

Solution

相当于将各个数字进行掩码操作，计算各个数组的同一个位上1的数量即可。

bin[]数组记录各个数字的各个位上的1的数量。
如果当前数字与1进行掩码操作后等于1，则将该位数量加一。
然后将当前数字向右移动一位，直至将所有的位都统计完。

最后返回各个位上的最大值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int largestCombination(int[] candidates) {
        int[] bin = new int[31];
        int res = 0;
        for(int candidate : candidates){
            int count = 0;
            while(count < 31){
                if((candidate & 1) == 1){
                    bin[count]++;
                }
                candidate = candidate >> 1; 
                count++;
            }
        }
        for(int time : bin){
            res = Math.max(res, time);
        }
        return res;
    }
}

Question

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Solution

进行按位和运算时，只要两个位不都是1就会为0。从left到right之间，如果left和right的前x位是一样的，那么两者之间必定有一个数字
在x位上为1，后面的位上为0。因此和这个数字进行按位和运算必定为0。
因此，我们只要保留前面两者相同的位的信息即可，后面均为0。

当left与right不相等时，将两者同时右移，并计算移动的总数。
当两者相等时，向左移动计算的总数的位数。就保留了其相同的前缀。

Code

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        
        while(left != right){
            left >>= 1;
            right >>= 1;
            count++;
        }
        return left << count;
    }
}

Solution 2

利用一串只有一个1的32位数字作为掩码，获得两个数字单独的位信息。
32位整数的第一位是符号位。因此我们的掩码从第1位开始直到第31位。
当对left和right进行该位的掩码操作后，如果两者相同，则掩码右移一位。
并将答案和当前位进行位或运算。（相当于保存当前位的位信息。）

如果不同，或者掩码变为0，则返回结果。

Code

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int mask = 1 << 30;
        int ans = 0;
        
        while(mask > 0 && (mask & left) == (mask & right)){
            ans |= (mask & left);
            mask >>= 1;
        }
        return ans;
    }
}

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

• For example, “ACGAATTCCG” is a DNA sequence.
  When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

哈希表 + 滑动窗口 + 位操作。
将四个字符映射到四个二进制字符上。这样字符串就可以用20bit表示。
这样就可以用一个整数来表示这四个字符。
然后采用哈希表记录出现次数。

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

class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        if(s.length() < L) return ret;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        int[] bin = new int[26];
        bin['A'-'A'] = 0;
        bin['T'-'A'] = 1;
        bin['C'-'A'] = 2;
        bin['G'-'A'] = 3;
        
        int x = 0;
        for(int i = 0; i < L-1; i++){
            x = (x << 2) | bin[s.charAt(i)-'A'];
        }
        
        for(int i = 0; i <= s.length() - L; i++){
            x = ((x << 2) | bin[s.charAt(i + L -1)-'A']) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.get(x) == 2) ret.add(s.substring(i, i+L)); 
        }
        return ret;
    }
}

遍历将字字符串加入哈希表并记录出现次数，然后返回出现次数大于1的字符串。
注意在循环时就可以直接添加结果到列表，这样可以减少操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        while(right <= s.length()){
            String sub = s.substring(left, right);
            map.put(sub, map.getOrDefault(sub, 0)+1);
            if(map.get(sub) == 2) ret.add(sub); 
            left++;
            right++;
        }
        return ret;
    }
}

问题
Reverse bits of a given 32 bits unsigned integer.

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

创建返回值ans。
每次向左移动一位ans，然后取n的尾数进行二进制或运算（相当于在尾部进行不进位的加和）。
然后将n向左移动一位。

• 二进制下的或运算只保留两数间较大的位。(0011 | 0110 = 0111)
• 二进制下的与运算只保留两数间皆为1的位。(0011 & 0110 = 0010)
• 掩码（Mask）是在二进制下进行与运算。以1作为掩码时，前面的31为皆为0，因此进行与运算后只保留最后一位。

因此(n & 1)相当于n的二进制与000…001运算，只保留n的尾数。
然后(ans << 1)向左移动一位，用 | 操作将n的尾数加入ans。

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans = (ans << 1) | (n & 1);
            n >>= 1;
        }
        return ans;
    }
}

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

位运算，对所有数值做二进制异或运算。
两个同样的值异或运算会等于0，最后和与单独的数字相等。

1
2
3
4
5
6
7
8
9

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int num : nums){
            ans = ans ^ num;
        }
        return ans;
    }
}

排序，然后遍历数组，如果第i个值不等于第i+1个则返回。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; i+=2){
            if(nums[i] != nums[i+1]){
                return nums[i];
            }
        }
        return nums[nums.length-1];
    }
}

问题
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

位运算，[n-1]的二进制数字为[n]的二进制数字退一位。
二者的与运算结果相当于二进制下[n]减少最右侧的1。
例如0100100的0100011
两者的与运算结果为0100000。相当于减少了一位1。
计算循环次数就可以得出1的总数。

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = (n & (n-1));
            count++;
        }
        return count;
    }
}

问题
Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

位运算，由于2^n^的二进制为[100…00]，当2^n^-1时，其二进制为[11..11]（少一位）。
两者进行按位与（&）运算，得到[000…00]，与0相等。

1
2
3
4
5
6
7
8

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}

递归，当（n <= 0）时，返回false。
当n等于1时，返回true。
当（n % 2）有余数时，返回false。
递归（n / 2）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        if (n == 1){
            return true;
        }
        if (n%2 != 0){
            return false;
        }
        return isPowerOfTwo(n/2);
    }
}