位运算

谁践踏了优雅 2023-12-29 06:20 140阅读 0赞

### 1、只出现一次的数字 ###

描述：  
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
说明：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？  
示例 1:  
输入: \[2,2,1\]  
输出: 1  
示例 2:

输入: \[4,1,2,1,2\]  
输出: 4

class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int res=nums[0];
            for(int i=1;i<nums.size();i++)
            {
                res^=nums[i];
            }
            return res;
        }
    };

### 2、只出现一次的数字 II ###

描述：  
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: \[2,2,3,2\]  
输出: 3  
示例 2:

输入: \[0,1,0,1,0,1,99\]  
输出: 99  
分析：  
还是利用位运算才有办法实现不用额外空间，就是遍历32次每次记录某位的出现的次数，如果不能被三整除，说明那个出现一次的就在该位有值，那么ans 或该位一下就可以了

class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int ans=0;
            for(int j=0;j<32;j++)
            {
                int tmp=1<<j;
                int res=0;
                for(int i=0;i<nums.size();i++)
                {
                    if(nums[i]&tmp)res++;
                }
                if(res%3!=0)ans|=tmp;
            }
            return ans;
        }
    };

### 3、位1的个数 ###

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011  
输出：3  
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。  
示例 2：

输入：00000000000000000000000010000000  
输出：1  
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。  
示例 3：

输入：11111111111111111111111111111101  
输出：31  
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。  
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int cnt=0;
            while(n)
            {   cnt++;
                n=n&(n-1);
            }
            return cnt;
        }
    };

### 4、给定一个整数，编写一个函数来判断它是否是 2 的幂次方。 ###

思路：如果是power of two, 则2进制表达中,有且仅有一个1. 可以通过移位来数1的个数, 这里用了一个巧妙的办法, 即判断 N & (N-1) 是否为0.

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

普通解法：

class Solution {
    public:
        bool isPowerOfTwo(int n) {
            if(n==1)return true;
            while(n&&n%2==0)
            {
                n=n/2;
                if(n==1)return true;
            }
            return false;
        }
    };

### 5、4的幂 ###

思路：1、num&(num-1) 判断一个数是否为2的幂数  
2、4的幂级数为1,4,16，即0001，0100,10000，也就是1出现在1,3,5,7。。。。位置上。0x55555555在32位系统里表示0b01010101010101010101010101010101。

return ((num & (num-1)) == 0) && num > 0 && ((num  & 0x55555555) != 0)

常规解法：

class Solution {
    public:
        bool isPowerOfFour(int num) {
           if(num==1)return true;
            while(num&&num%4==0)
            {
                num=num/4;
                if(num==1)return true;
            }
            return false;
        }
    };

### 5、找不同 ###

给定两个字符串 s 和 t，它们只包含小写字母。  
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。  
请找出在 t 中被添加的字母。  
示例:  
输入：  
s = “abcd”  
t = “abcde”  
输出：  
e  
解释：  
‘e’ 是那个被添加的字母。

class Solution {
    public:
        char findTheDifference(string s, string t) {
            int ans=0;
            for(int i=0;i<s.length();i++)
                ans^=(s[i]-'a');
            for(int j=0;j<t.length();j++)
                ans^=(t[j]-'a');
            return 'a'+ans;
        }
    };

### 6、字母大小写全排列 ###

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:  
输入: S = “a1b2”  
输出: \[“a1b2”, “a1B2”, “A1b2”, “A1B2”\]

输入: S = “3z4”  
输出: \[“3z4”, “3Z4”\]

输入: S = “12345”  
输出: \[“12345”\]  
注意：

S 的长度不超过12。  
S 仅由数字和字母组成。

class Solution {
    public:
        vector<string> letterCasePermutation(string S) 
        {
            int n=S.length();
            vector<string> res{""};
            for(int i=0;i<n;i++)
            {
                int len=res.size();
                if(S[i]>='0' && S[i]<='9')
                {
                    for(int j=0;j<len;j++)
                    {
                        res[j].push_back(S[i]);
                    }
                }
                else
                {
                    for(int j=0;j<len;j++)
                    {
                        res.push_back(res[j]);
                        res[j].push_back(tolower(S[i]));
                        res[j+len].push_back(toupper(S[i]));
                    }
                }
            }
            return res;        
        }
    };

### 7、缺失数字 ###

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。  
示例 1:  
输入: \[3,0,1\]  
输出: 2  
示例 2:  
输入: \[9,6,4,2,3,5,7,0,1\]  
输出: 8  
说明:  
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int n=nums.size();
            int a=0;
            int b=0;
            for(int i=1;i<=n;i++)
            {
                a+=i;
                b+=nums[i-1];
            }
            return a-b;
        }
    };

### 8、两整数之和 ###

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

输入: a = 1, b = 2  
输出: 3  
示例 2:

输入: a = -2, b = 3  
输出: 1

class Solution {
    public:
        int getSum(int a, int b) {
             if(b == 0) {
                 return a;
             }
            int sum = a ^ b; //相加但不进位
            int carry = (unsigned int)(a & b) << 1; //进位但不相加
            return getSum(sum, carry); //递归
        }
    };

### 9、二进制表示中质数个计算置位 ###

描述：  
给定两个整数 L 和 R ，找到闭区间 \[L, R\] 范围内，计算置位位数为质数的整数个数。  
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）  
示例 1:  
输入: L = 6, R = 10  
输出: 4  
解释:  
6 -> 110 (2 个计算置位，2 是质数)  
7 -> 111 (3 个计算置位，3 是质数)  
9 -> 1001 (2 个计算置位，2 是质数)  
10-> 1010 (2 个计算置位，2 是质数)  
示例 2:  
输入: L = 10, R = 15  
输出: 5  
解释:  
10 -> 1010 (2 个计算置位, 2 是质数)  
11 -> 1011 (3 个计算置位, 3 是质数)  
12 -> 1100 (2 个计算置位, 2 是质数)  
13 -> 1101 (3 个计算置位, 3 是质数)  
14 -> 1110 (3 个计算置位, 3 是质数)  
15 -> 1111 (4 个计算置位, 4 不是质数)  
注意:  
L, R 是 L <= R 且在 \[1, 10^6\] 中的整数。  
R - L 的最大值为 10000。

思路：  
step1：把L到R的数字依次换算成二进制  
step2：把二进制数中的1统计出来，c  
step3：判断c是不是素数

class Solution {
    public:
        int countPrimeSetBits(int L, int R) {
            int res=0;
            for(int i=L;i<=R;i++)
            {
                int tmp=i;
                int cnt=0;
                while(tmp)
                {
                    if(tmp%2)
                        cnt++;
                    tmp=tmp/2;
                }
                if(isprime(cnt))res++;
            }
            return res;
        }
        bool isprime(int n){
    	if(n==1) return false;
    	else if(n==2) return true;
    	else{
    		for(int i=2;i<=n/2;i++){
    			if(n%i==0){
    				return false;
    				break;
    			}
    		}
    	}
    	return true;
    }
    };

### 10、交替位二进制数 ###

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

输入: 5  
输出: True  
解释:  
5的二进制数是: 101  
示例 2:

输入: 7  
输出: False  
解释:  
7的二进制数是: 111  
示例 3:

输入: 11  
输出: False  
解释:  
11的二进制数是: 1011  
示例 4:

输入: 10  
输出: True  
解释:  
10的二进制数是: 1010  
思路：  
从低到高依次获取二进制中的每一位，判断当前获取的是否与前一个相同，如果相同就返回false

class Solution {
    public:
        bool hasAlternatingBits(int n) {
            if(n==0)return false;
            int tmp=n%2;
            n=n/2;
            while(n)
            {
                if(tmp==n%2)return false;
                tmp=n%2;
                n=n/2;
            }
            return true;
        }
    };

### 11、数字的补数 ###

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

给定的整数保证在32位带符号整数的范围内。  
你可以假定二进制数不包含前导零位。  
示例 1:

输入: 5  
输出: 2  
解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。  
示例 2:

输入: 1  
输出: 0  
解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。  
思路：记录位数，并对当前求得的（1或者0）取反，最后相加即可。

class Solution {
    public:
        int findComplement(int num) {
            int res=0;
            int n=0;
            int c=0;
            while(num)
            {
                n=1-(num%2);
                num=num/2;
                res+=pow(2,c)*n;
                c++;
            }
                return res;
        }
    };

### 12、颠倒二进制位 ###

依次将n的末尾位给result的末尾位，并且result向左移31次

class Solution {
    public:
        uint32_t reverseBits(uint32_t n) {
            int res=0;
            int i=0;
            while(i<32)
            {
                int tmp=n&0x01;
                res=(res<<1)|tmp;
                n=n>>1;
                i++;
            }
            return res;
        }
    };

### 13、汉明距离 ###

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：  
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:  
1 (0 0 0 1)  
4 (0 1 0 0)  
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

class Solution {
    public:
        int hammingDistance(int x, int y) {
           int sum=x^y;
           int count=0;
           while(sum)
           {
               sum&=(sum-1);
               count++;
           }
            return count;
        }
    };

### 14、汉明距离总和 ###

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）  
所以答案为：  
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.  
注意:

数组中元素的范围为从 0到 10^9。  
数组的长度不超过 10^4。

class Solution {
    public:
        int totalHammingDistance(vector<int>& nums) {
            int res=0;
            if(nums.size()==0)return res;
            for(int i=0;i<nums.size();i++)
            {
                for(int j=i+1;j<nums.size();j++)
                {
                    res+=dis(nums[i],nums[j]);
                }
            }
            return res;
        }
         int dis(int x, int y) {
           int sum=x^y;
           int count=0;
           while(sum)
           {
               sum&=(sum-1);
               count++;
           }
            return count;
        }
    };

超时  
分析：这种算法存在大量的重复计算。一个数只有32位，每一位不是0就是1，我们统计所以所有数每一位是0，1个数，这一位不同的情况数就是两者的乘积。然后将32为求和即可。

class Solution {
    public:
        int totalHammingDistance(vector<int>& nums) {
           int res=0;
           for(int i=0;i<32;i++)
           {
               int cnt=0;
               for(auto num:nums)
               {
                   cnt+=(num>>i)&1;
               }
               
               res+=cnt*(nums.size()-cnt);
           }
            return res;
        }
    };

### 15、数字转换为十六进制数 ###

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。  
注意:  
十六进制中所有字母(a-f)都必须是小写。  
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。  
给定的数确保在32位有符号整数范围内。  
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。  
示例 1：

输入:  
26

输出:  
“1a”  
示例 2：

输入:  
\-1

输出:  
“ffffffff”

class Solution {
    public:
        string toHex(int num) {
            if(num == 0) return "0";
            string ans;
            unsigned int n;
            n = (unsigned int)num;
            
            while(n > 0) {
                int a = n%16;
                string c;
                n /= 16;
                if(a > 9)
                    c += 'a' + a-10;
                else 
                    c += '0' + a;
                ans.insert(0, c);
            }
            return ans;
        }
    };