本文主要记录二进制的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。
一、二进制计数
461. 汉明距离（简单难度）
class Solution {
public:
int hammingDistance(int x, int y) {
// 方法一：进制转换
// int count=0;
// if(x==y)
// return 0;
// // 同时取位
// while(x!=0||y!=0){
// if(x%2!=y%2)
// count++;
// x=x/2;
// y=y/2;
// }
// return count;
// 方法二：位运算
int count=0;
int a=x^y;// 异或运算，相同为0，不同为1
while(a){
count+=a&1;// 查看最后一位是否是1
a>>=1;// 右移1位
}
return count;
}
};
191. 位1的个数（简单难度）
剑指 Offer 15. 二进制中1的个数（简单难度）
方法一：
class Solution {
public:
int hammingWeight(uint32_t n) {
string res;
if(n==0) res="0";
while(n>0){
res=to_string(n%2)+res;
n=n/2;
}
int num=0;
for(char c:res){
if(c=='1') num++;
}
return num;
}
};
方法二：
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
count += n & 1;
n>>=1;
}
return count;
}
};
338. 比特位计数（简单难度）
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数（简单难度）
class Solution {
public:
// 十进制转换为2二进制
string ten2k(int num,int k=2){
if(num==0) return "0";
string ans;
while(num){
ans= to_string(num%k)+ans;
num/=k;
}
return ans;
}
vector<int> countBits(int n) {
vector<int> res;
for(int i=0;i<=n;i++){
string bits=ten2k(i);//二进制的字符串
int num=0;//统计字符串中1的个数
for(int j=0;j<bits.length();j++){
if(bits[j]=='1') num++;
}
res.push_back(num);
}
return res;
}
};
190. 颠倒二进制位（简单难度）
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
int power=31;
while(n){
rev+=(n&1)<<power;//左移32位
n>>=1;
power--;
}
return rev;
}
};
二、二进制转换
1290. 二进制链表转整数（简单难度）
class Solution {
public:
// 二进制转十进制
int getDecimalValue(ListNode* head) {
vector<int> arr;
// 将链表元素加入数组中
ListNode* p=head;
while(p){
arr.push_back(p->val);
p=p->next;
}
// 二进制转换为十进制
int n=arr.size();
int k=1;
int sum=0;
for(int i=n-1;i>=0;i--){
sum+=arr[i]*k;
k*=2;
}
return sum;
}
};
693. 交替位二进制数（简单难度）
class Solution {
public:
string ten2k(int n,int k=2){
if(n==0) return "0";
string res;
while(n>0){
res=to_string(n%k)+res;
n=n/k;
}
return res;
}
bool hasAlternatingBits(int n) {
string kbit=ten2k(n);
char flag='0';
for(int i=1;i<kbit.length();i++){
if(kbit[i]==kbit[i-1]) return false;
}
return true;
}
};
1009. 十进制整数的反码（简单难度）
476. 数字的补数（简单难度）
class Solution {
public:
string ten2k(int n,int k=2){
if(n==0) return "0";
string res;
while(n>0){
res=to_string(n%k)+res;
n=n/k;
}
return res;
}
int k2ten(string n,int k=2){
int sum=0;
long a=1;// 注意，必须为整型
for(int i=n.length()-1;i>=0;i--){
sum+=(n[i]-'0')*a;
a*=k;
}
return sum;
}
int bitwiseComplement(int num) {
string kbit = ten2k(num);//10进制转换为二进制
string res="";
for(char c:kbit){
if(c=='1'){
res+='0';
}
else {
res+='1';
}
}
int n=k2ten(res);
return n;
}
};
三、非二进制转换
504. 七进制数（简单难度）
class Solution {
public:
string convertToBase7(int num) {
if(num==0) return "0";
string res;
// 处理正数
int tempNum=abs(num);//如果num为负数，变为正数
while(tempNum>0){
res=to_string(tempNum%7)+res;
tempNum=tempNum/7;
}
if(num<0) res.insert(res.begin(),'-');
return res;
}
};
405. 数字转换为十六进制数（简单难度）
class Solution {
public:
string toHex(int n) {
if(n==0) return "0";
unsigned num = n;//转换为无符号
string res;
while(num>0){
int base=num%16;
char c='0';
if(base>9) {
c=base-10+'a';
}else{
c=base+'0';
}
res+=c;
num=num/16;
}
reverse(res.begin(),res.end());
return res;
}
};
171. Excel 表列序号（简单难度）
这道题要求将Excel 表中的26个的由大写字母组成的列名称转换成相对应的列序号，因此本质就是一道26进制转换为10进制的题目，但是这道题与标准的进制转换（0-25）不同，因为Excel表的列序号是1到26，需要特殊处理。
class Solution {
public:
int titleToNumber(string columnTitle) {
int sum=0;
long k=1;//幂,幂要设置为long
for(int i=columnTitle.length()-1;i>=0;i--){
sum+=(columnTitle[i]-'A'+1)*k;
k*=26;
}
return sum;
}
};
168. Excel表列名称（简单难度）
class Solution {
public:
string convertToTitle(int n) {
// 10进制转26进制的模板，正常26进制是0-25，该题是1-26，
string res="";
while(n>0){
--n;//每一位都多了1，此处-1使其可以用正常的26进制代码处理
res+=n%26+'A';//将数字字符转换为大写字母字符,'A'是65,'0'是48
n=n/26;
}
reverse(res.begin(),res.end());//反转序列
return res;
}
};
四、数位分离
1281. 整数的各位积和之差（简单难度）
class Solution {
public:
int subtractProductAndSum(int n) {
int sum=0;
int x=1;
while(n>0){
sum+=n%10;
x*=n%10;
n=n/10;
}
return x-sum;
}
};
258. 各位相加（简单难度）
class Solution {
public:
int addDigits(int num) {
while(num>=10)// 大于等于1位数
{
int sum=0;
while(num>0){
sum+=num%10;
num=num/10;
};
num=sum;
}
return num;
}
};
1945. 字符串转化后的各位数字之和（简单难度）
class Solution {
public:
int getLucky(string s, int k) {
// 转换成数字
string str="";
for(int i=0;i<s.length();i++){
int num=s[i]-'0'-48;
str+=to_string(num);
}
// 重复转换操作k次
int sum=0;
while(k)//
{
sum=0;
for(int i=0;i<str.length();i++){
sum+=str[i]-'0';
}
str=to_string(sum);
k--;
}
return sum;
}
};
1837. K 进制表示下的各位数字总和（简单难度）
class Solution {
public:
int sumBase(int n, int k) {
// 从10进制转换为k进制
string kbits="";
if(n==0) kbits="0";
while(n>0){
kbits=to_string(n%k)+kbits;
n=n/k;
}
// 各位累和
int sum=0;
for(char c:kbits) sum+=c-'0';
return sum;
}
};
五、数组中元素出现的次数
1、一个数出现1次，其余数都出现2次
136. 只出现一次的数字（简单难度）
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 方法一：位运算
// 数组中一定有奇数个元素，数组中的全部元素进行异或运算，结果即为只出现一次的数字
// int res=0;
// for(int num:nums) res^=num;
// return res;
// 方法二：位运算
int res=0;
for(int i=0;i<32;i++){
int mask=1<<i;//从右向左取第i位
int cnt = 0;//第i位出现的次数
// 遍历整个数组后的第i位出现了几次1
for (int num:nums) {
if ((num & mask) != 0) {
cnt++;
}
}
// 如果第i位没有出现3次则保留
if (cnt % 2 != 0) {
res |= mask;
}
}
return res;
// // 方法二：哈希法
// unordered_map<int,int> map;// 数字和出现次数
// // 遍历数组一遍统计频率
// for(int num:nums){
// map[num]++;
// }
// // 遍历哈希表
// for(auto it=map.begin();it!=map.end();++it){
// if(it->second==1)
// return it->first;
// }
// return -1;
}
};
2、一个数出现1次，其余数都出现3次
137. 只出现一次的数字 II（中等难度）
剑指 Offer 56 - II. 数组中数字出现的次数 II（中等难度）
剑指 Offer II 004. 只出现一次的数字（中等难度）
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 方法一：位运算(异或)
// int ones=0;twos=0;
// for(int num:nums){
// ones=ones^num&(~twos);//x & ~x = 0;// num，0,0
// twos=twos^num&(~ones);//x & ~0 = x;// 0，num，0
// }
// return ones;
// 方法二：位运算
int res=0;
for(int i=0;i<32;i++){
int mask=1<<i;//从右向左取第i位
int cnt = 0;//第i位出现的次数
// 遍历整个数组后的第i位出现了几次1
for (int num:nums) {
if ((num & mask) != 0) {
cnt++;
}
}
// 如果第i位没有出现3次则保留
if (cnt % 3 != 0) {
res |= mask;
}
}
return res;
// 方法二：哈希法
// unordered_map<int,int> map;// 数字和出现次数
// // 遍历数组一遍统计频率
// for(int num:nums){
// map[num]++;
// }
// // 再次遍历遍历字符串
// for(int num:nums){
// if(map[num]==1)
// return num;
// }
// return -1;
}
};
3、两个数出现1次，其余数都出现2次
260. 只出现一次的数字 III（中等难度）
剑指 Offer 56 - I. 数组中数字出现的次数（中等难度）
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res(2,0);
int aob=0;
for(int num:nums){
aob^=num;
}
// 取出最后一位
int lastBit = (aob == INT_MIN ? aob : aob & (-aob));// 防止溢出
for (int num : nums) {
// 分成2个数
if ((lastBit & num) != 0)
res[0] ^= num;
else
res[1] ^= num;
}
return res;
}
};
六、四则运算
1、两数加法
剑指 Offer 64. 求1+2+…+n
class Solution {
public:
int sumNums(int n) {
if(n==0) return 0;
return n+sumNums(n-1);
}
};
371. 两整数之和（简单难度）
剑指 Offer 65. 不用加减乘除做加法（简单难度）
面试题 17.01. 不用加号的加法（简单难度）
class Solution {
public:
int getSum(int a, int b) {
// 当进位部分不为0，说明需要继续加
while (a != 0) {
int temp = a ^ b;//非进位部分（没有添加进位部分），按位异或，
//异或这里可看做是相加但是不显现进位，比如5 ^ 3
/*0 1 0 1
0 0 1 1
------------
0 1 1 0 */
a = ((unsigned int)a & b) << 1; //进位部分，都是1是发生进位，对有符号左移的溢出保护处理
//相与为了让进位显现出来，比如5 & 3
/* 0 1 0 1
0 0 1 1
------------
0 0 0 1
上面的最低位1和1相与得1*/
b = temp;
}
return b;
}
};
67. 二进制求和（简单难度）
剑指 Offer II 002. 二进制加法（简单难度）
class Solution {
public:
string addBinary(string a, string b) {
string res;
// 从右向左同时遍历2个可能不等长的字符串
int i=a.length()-1;
int j=b.length()-1;
bool carry=false;
int sum=0;
while(i>=0||j>=0){
sum=0;
if(i>=0) sum+=a[i--]-'0';
if(j>=0) sum+=b[j--]-'0';
if(carry) sum+=1;
res =to_string(sum%2)+res;
carry=sum>=2?true:false;
}
// 如果有多余的进位
if(carry) res =to_string(1)+res;
return res;
}
};
2、两数除法
29. 两数相除（中等难度）
剑指 Offer II 001. 整数除法（简单难度）
class Solution {
public:
/* 被除数÷除数=商...余数,进而推导得出：商×除数+余数=被除数
思路：找到一个足够大的数x,x足够接近商，使得x*除数<=被除数，即(被除数/x)>=除数(x必须为正数)
因为不可以使用*和/,就只可使用位移，计算机在做位移时效率特别高，向左移1相当于乘以2，向右位移1相当于除以2
(被除数/x)>=除数(x必须为正数)，可以表示为(被除数>>i)>=除数,x=2^i,因为x足够大，所以i应该从最大值不断减少
i的取值范围为[0,31],注意：被除数和除数都需要转换为unsigned int
以100/3为例，x=2^n是1，2，4，8...2^31这种数
当n=31时，x特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
当n=5时，x=32，100/32=3, 刚好是大于等于3的，说明真正的商res>=x，我们可以先res+=x;
将100-32*3=4，此时被除数变为了4，接下来继续处理4：
当n=0时，x=1，4/1=4,刚好大于等于3，说明res+=1，被除数4-1*3=1，此时n已到最小值，结束商res=33
这其中得处理一些特殊的数，比如divisor是不能为0的，INT_MIN和INT_MAX*/
int divide(int dividend, int divisor) {
if(dividend==0) return 0;// 被除数为0，直接返回0
if (dividend==INT_MIN &&divisor==-1) return INT_MAX;// 被除数是最小值，除数是-1，返回最大值
bool negative=(dividend^divisor)<0;//用异或来计算是否符号相异
// 将有符号整数转为无符号整数
unsigned int t = abs(dividend);//被除数
unsigned int d = abs(divisor);// 除数
unsigned int res = 0;// 商
// i从大到小，商从小到大
for (int i = 31; i >= 0; i--) {
// 计算t除于2^i的商
if((t>>i)>=d) {//找出足够大的数2^n*divisor
res+=((unsigned int)1)<<i;//商>=1*2^n
t-= d<<i;//将被除数-2^n*divisor
}
}
//特殊数不能将unsigned int转为int
if(res == INT_MIN) return INT_MIN;
else return negative?-(int)res:(int)res;//符号相异取反
}
};
####