位移操作

作者: Phoebe_Liu | 来源:发表于2018-12-17 20:03 被阅读0次

基础：

<< : 左移运算符，num << 1,相当于num乘以2
>> : 右移运算符，num >> 1,相当于num除以2
>>> : 无符号右移，忽略符号位，空位都以0补齐
原码，反码，补码。正数的原码，反码，补码都一样，负数的反码是对除了符号位（最高位）对原码取反，补码是对反码+1
负数的带符号移位时，最高位——符号位，不变

判断2的次方数
如果一个数是2的次方数的话，根据上面分析，那么它的二进数必然是最高位为1，其它都为0，那么如果此时我们减1的话，则最高位会降一位，其余为0的位现在都为变为1，那么我们把两数相与，就会得到0，用这个性质也能来解题，而且只需一行代码就可以搞定，如下所示

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

判断3的次方数
高中学过的换底公式为log_ab = log_cb / log_ca，那么如果n是3的倍数，则log₃n一定是整数，我们利用换底公式可以写为log₃n = log₁₀n / log₁₀3，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log₁₀n / log₁₀3是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断

class Solution {
public:
     public boolean isPowerOfFour(int num) {
        return (num>0 && (isIntegerForDouble(Math.log(num)/ Math.log(3))) );
    }
    
    public static boolean isIntegerForDouble(double obj) {  
        double eps = 1e-10;  // 精度范围  
        return obj-Math.floor(obj) < eps;  
    } 
};

判断4的次方数
同上，log的换底公式
按位翻转
思路：每次取最右位的数字，然后判断是1还是0

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

找到数组里落单的一个数字——数组里除了一个数字出现1次之外，其他都出现了2次
采用异或的方法。

class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null || nums.length == 0)
            return -1;
        
        int result = 0;
        
        for(int cur: nums){
            result ^= cur;
        }
        
        return result;
    }
}

找到s和t字符串之间，唯一不同的那个元素char——思路同6

class Solution {
    public char findTheDifference(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        
        
        int result = 0;
        for(char cur: a){
            result ^= cur;
        }
        
         for(char cur: b){
            result ^= cur;
        }
        
        return (char) result;
    }
}

给出3*n + 1 个非负整数，除其中一个数字之外其他每个数字均出现三次，找到这个数字
思路：利用位操作 Bit Operation 来解此题。建立一个32位的数字，来统计输入数组各元素之和。
需要每次对各元素同一bit位进行加和，如果这个数字出现过3次，那么%3=0；如果只出现过1次，%3！=0，而且余多少，改数字的这bit位上就是多少。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        
        for(int i =0;i<32; i++){
            int sum = 0;
            
            for(int cur: nums){
                sum += (cur >> i) & 1;
            }
            result |= (sum % 3) << i;
        }
        
        return result;
    }
}

求子集，列出所有结果——这个不是bit operation，是数组的移位

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null || nums.length ==0)
            return [];
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        
        for(int cur: nums){
            int size = res.size();
            
            for(int i=0; i<size; i ++){
                List<Integer> cur_list = new ArrayList<>(res.get(i));
                cur_list.add(cur);
                res.add(cur_list);
            }
        }
        
        return res;
    }
}

求重复的DNA序列
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"]
思路：A: 0100 0001　　C: 0100 0011　　G: 0100 0111　　T: 0101 0100

由于我们的目的是利用位来区分字符，当然是越少位越好，通过观察发现，每个字符的后三位都不相同，故而我们可以用末尾三位来区分这四个字符。而题目要求是10个字符长度的串，每个字符用三位来区分，10个字符需要30位，在32位机上也OK。为了提取出后30位，我们还需要用个mask，取值为0x7ffffff，用此mask可取出后27位，再向左平移三位即可。算法的思想是，当取出第十个字符时，将其存在哈希表里，和该字符串出现频率映射，之后每向左移三位替换一个字符，查找新字符串在哈希表里出现次数，如果之前刚好出现过一次，则将当前字符串存入返回值的数组并将其出现次数加一，如果从未出现过，则将其映射到1。为了能更清楚的阐述整个过程，我们用题目中给的例子来分析整个过程：

首先我们取出前九个字符AAAAACCCC，根据上面的分析，我们用三位来表示一个字符，所以这九个字符可以用二进制表示为001001001001011011011，然后我们继续遍历字符串，下一个进来的是C，则当前字符为AAAAACCCCC，二进制表示为001001001001011011011011，然后我们将其存入哈希表中，用二进制的好处是可以用一个int变量来表示任意十个字符序列，比起直接存入字符串大大的节省了内存空间，然后再读入下一个字符C，则此时字符串为AAAACCCCCA，我们还是存入其二进制的表示形式，以此类推，当某个序列之前已经出现过了，我们将其存入结果res中即可

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        
        if(s==null || s.length() < 10)
            return res;
        
        char[] chars = s.toCharArray();
        Set<Integer> combinesIntegers = new HashSet<Integer>();
        
        int mask = 0x7ffffff; // 掩码：能够提取低27位（也就是后面9个字符）
        int i =0; // 数组遍历的角标
        int cur = 0; // 当前窗口为10的字符串，用一个数字表示的结果
        
        while(i<9){
            cur = (cur << 3) | (chars[i++] & 7); // ACGT，每个字母用3个数字表示。所以用7(0b111即可作为当前字母的提取掩码)
            // i++;
        }
        
        while(i < s.length()){
            cur = ((cur & mask) << 3) | (chars[i++] & 7);
            
            if(combinesIntegers.contains(cur)){ // 如果哈希表里已有，说明之前这个四个字母的组合已经出现过，即可加入返回队列里
                String target = s.substring(i-10,i);
                if(res.contains(target) == false){ // 判断，返回队列不要有重复数据
                    res.add(target);
                }
            }else{
                combinesIntegers.add(cur);
            }
            
            // i++;
        }
        
        return res;
    }
}

数字范围相与
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.
只要写代码找到m和n的左边公共的部分即可

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if(m == n)
            return m;
        
        int mask = 0xffffffff;
        while((m & mask) != (n & mask)){
            mask = mask << 1;
        }
        return m & mask;
    }
}

给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
分析：

异或：两个相同数字异或，结果为0；0与任意数异或，结果是其本身
a & (-a)：可以得到这个数字里某一位为1的值。 is a trick to extract the lowest set bit of i
a & 1: 获取数字最低位
解题：（1）从前往后遍历，所有数字异或的结果=那两个特别数字异或的结果xor
（2）将nums分为两大阵营：将xor转化为只保留某一位为1、其他为0的数字，然后与各个nums数字与操作。=1 PK =0，自然分为两大阵营。

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0; // 用于保存异或结果
        int group0=0; // 用于保存第一组的异或结果
        int group1=0; // 用户保存第二组的异或结果
        
        for(int cur: nums){
            xor ^= cur;
        }
        xor = xor &(-xor); // 这个公式，可以求出xor里某一位=1的数字
        
        for(int cur: nums){
            if( (xor & cur) == 0){
                group0 ^= cur;
            }
            else{
                group1 ^= cur;
            }
        }
        
        int[] returns = new int[2];
        returns[0] = group0;
        returns[1] = group1;
        
        return returns;
    }
}

单词长度的最大积——让我们求两个没有相同字母的单词的长度之积的最大值
给定一个字符串数组 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"。

因为题目中说都是小写字母，那么只有26位，一个整型数int有32位，我们可以用后26位来对应26个字母，若为1，说明该对应位置的字母出现过；进而我们也可以用一个int数字表示一个英文单词。
这样判断两个单词没有共同字母的条件是：这两个int数相与结果=0

class Solution {
    public int maxProduct(String[] words) {
        if(words == null || words.length <= 1 ){
            return 0;
        }
        
        int max_product = 0;
        
        List<Integer> mask = new ArrayList<Integer>(); // 因为都是小写字母，总数最多26个。所以可以用一个32位的Int，用其二进制表示法 表示一个字母，而且bit中为1的只有一个。因此一个单词，也同样可以用一个二进制数表示。
        
        for(int i =0 ; i< words.length;i++){
            // 计算 当前单词的mask值
            int cur_mask = 0;
            for(char cur: words[i].toCharArray()){
                cur_mask |= (1 << (cur-'a'));
            }
            mask.add(cur_mask);
            
            // 遍历i之前的那些数组
            for(int j =0; j <i; j++){
                if((mask.get(i) & mask.get(j)) == 0){
                    max_product = Math.max(max_product, words[i].length() * words[j].length());
                }
            }
            
        }
        
        return max_product;
        
    }
}

Sum of Two Integers——不用+、-，但要求计算出两个数字之和

两个数字如果忽略进位求和可用异或计算
两个数字的进位可用与计算

class Solution {
    public int getSum(int a, int b) {
        int xor = a ^ b;
        int carray = (a & b) <<1 ;
        
        
        if(carray != 0 ){
            return getSum(xor, carray);
        }
        return xor;
    }
}

将数字转换为16进制——给定一个整数，写一个函数将其转换为16进制，不能用系统自带的进制转换函数
mask固定

class Solution {
    public String toHex(int num) {
        if(num == 0) {
            return "0";
        }
        String ans = "";
        int len = 0;
        while(num != 0 && len < 8) {
            int bit = num & 15;
            if(bit < 10) {
                ans = (char)('0' + bit) + ans;
            }
            else {
                ans = (char)('a' + bit - 10) + ans;
            }
            num >>= 4;
            len++;
        }
        return ans;
    }
}

整数替换
If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
思路：
利用bit位的操作。如果这个数偶数，那么末位的bit位一定是0。如果一个数是奇数，那么末位的bit位一定是1。对于偶数，操作是直接除以2。
对于奇数的操作:
如果倒数第二位是0，那么n-1的操作比n+1的操作能消掉更多的1。
1001 + 1 = 1010
1001 - 1 = 1000
如果倒数第二位是1，那么n+1的操作能比n-1的操作消掉更多的1。
1011 + 1 = 1100
1111 + 1 = 10000

public int integerReplacement(int n) {
    // 处理大数据的时候tricky part, 用Long来代替int数据
    long N = n;
    int count = 0;
    while(N != 1) {
        if(N % 2 == 0) {
            N = N >> 1;
        }
        else {
            // corner case;
            if(N == 3) {
                count += 2;
                break;
            }
            N = (N & 2) == 2 ? N + 1 : N - 1;
        }
        count ++;
    }
    return count;
}

x&(-x):
如果x是奇数，则返回1
如果x是偶数，则返回最右bit=1的数字，该数也是：能整除这个偶数的最大的2的幂(即： y = x & -x , 则 x % y = 0, 且 y = 2 ^ k). 例如x=12时，12&(-12)=0100=4

i & (~i + 1) is a trick to extract the lowest set bit of i.

位移操作

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读