昨晚 Win10 更新 2h 都没有更新完,然后电脑因为没电关机了。。重启后恢复出厂设置都无效
还好自己用 PE 救回来了,怕重蹈覆辙,把最近的记录的东东都搬到博客上了
仅为个人学习记录,如有错误欢迎指正(毕竟也都是随笔记录
目录
前言
逻辑代数与位运算的关系
名称 | 逻辑代数 | 位运算 |
---|---|---|
按位与 | A · B | A & B |
按位或 | A + B | A | B |
逻辑非 | A' | !A |
按位异或 | A ⊕ B | (A ^ B) |
按位异或非 | A ⊙ B | !(A ^ B) |
(b & c) ^ (a & c) = c & (a ^ b)
(a ^ c) & (b ^ c) = (a & b) ^ c
逻辑代数公式
A ⊕ B = AB' + A'B
即 (A ^ B) = (A & ~B) | (~A & B)
A ⊙ B = AB + A'B'
二进制加法
S = A ⊕ B ⊕ Cin
Cout = (A · B) + (B · Cin) + (A · Cin)
可换算 Cout,式子如下:
Cout = (A · B) + (Cin · (A + B))
也可用一个异或门来代替或门对其中两个输入信号进行求和
Cout = (A · B) + (Cin · (A ⊕ B))
换成位运算即
init: C = Cout = Cin = 0
s = a ^ b ^ c
c = (a & b) | (c & (a ^ b))
例题
class Solution {
public:
string addBinary(string a, string b) {
int lena = a.size(), lenb = b.size();
int n = max(lena, lenb) + 1;
int ai, bi, s, c = 0;
int i = 0;
string res(n, 0);
for(; i < n; ++i) {
ai = (lena - i - 1 >= 0 ? a[lena - i - 1] - '0' : 0);
bi = (lenb - i - 1 >= 0 ? b[lenb - i - 1] - '0' : 0);
s = ai ^ bi ^ c;
c = (ai & bi) | (c & (ai ^ bi));
res[n - i - 1] = s + '0';
}
if('0' == res[0]) res.erase(res.begin());
return res;
}
};
统计n中1的个数
0xAAAAAAAA = 10101010101010101010101010101010
0x55555555 = 01010101010101010101010101010101(奇数位为1,以1位为单位提取奇偶位)
0xCCCCCCCC = 11001100110011001100110011001100
0x33333333 = 00110011001100110011001100110011(以“2位”为单位提取奇偶位)
0xF0F0F0F0 = 11110000111100001111000011110000
0x0F0F0F0F = 00001111000011110000111100001111(以“8位”为单位提取奇偶位)
0xFFFF0000 = 11111111111111110000000000000000
0x0000FFFF = 00000000000000001111111111111111(以“16位”为单位提取奇偶位)
例如:32位无符号数的1的个数可以这样数:
int count_one(unsigned long n){
//0xAAAAAAAA,0x55555555分别是以“1位”为单位提取奇偶位
n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
//0xCCCCCCCC,0x33333333分别是以“2位”为单位提取奇偶位
n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);
//0xF0F0F0F0,0x0F0F0F0F分别是以“4位”为单位提取奇偶位
n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);
//0xFF00FF00,0x00FF00FF分别是以“8位”为单位提取奇偶位
n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF);
//0xFFFF0000,0x0000FFFF分别是以“16位”为单位提取奇偶位
n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF);
return n;
}
举个例子吧,比如说我的生日是农历2月11,就用211吧,转成二进制:
n = 11010011
计算n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
得到 n = 10010010
计算n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);
得到 n = 00110010
计算n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);
得到 n = 00000101 -----------------无法再分了,那么 5 就是答案了
倒置二进制位
分治法
int M1 = 0x55555555; //01010101010101010101010101010101
int M2 = 0x33333333; //00110011001100110011001100110011
int M3 = 0x0f0f0f0f; //00001111000011110000111100001111
int M4 = 0x00ff00ff; //00000000111111110000000011111111
int M5 = 0x0000ffff; //00000000000000001111111111111111
n = (n >> 16) & M5 | (n & M5) << 16;
n = (n >> 8) & M4 | (n & M4) << 8;
n = (n >> 4) & M3 | (n & M3) << 4;
n = (n >> 2) & M2 | (n & M2) << 2;
n = (n >> 1) & M1 | (n & M1) << 1;
return n;
对于正整数的模运算
等于 n % k,这里 k 必须等于 2m才有用
公式
n & ((1 << k) - 1)
判断n是否是2的正整数幂
公式
n > 0 && !(n & (n - 1))
这里题目如果规定测试用例都是正整数,那么可以简写成 n && !(n & (n - 1))
引申题
-
判断 n 是否是 4 的正整数幂
(n & 0x55555555) && !(n & (n - 1)) && n;