1. 位运算与进制基础
位运算的奇淫技巧:
- 判断奇偶数
- 获取二进制位是1或0
- 交换两个整数变量的值
- 不用判断语句,求整数的绝对值
- >>和<<运算符将二进制位进行右移或者左移操作
- >>>运算符将用0填充高位;>>运算符用符号位填充高位，没有<<<运算符
- 对于int型,1<<35与1<<3相同的
- 与:都为1结果为1;或:有一个为1结果为1；异或:二者不同时结果为1
2. 几个有趣的位操作
1.利用或操作 | 和空格将英文字符转换为小写
('a' | ' ') = 'a' ('A' | ' ') = 'a'
2. 利用与操作 & 和下划线将英文字符转换为大写
1. ('b' & '_') = 'B' 2. ('B' & '_') = 'B'
3.利用异或操作 ^ 和空格进行英文字符大小写互换
1. ('d' ^ ' ') = 'D' 2. ('D' ^ ' ') = 'd'
4.判断两个数是否异号
int x = -1, y = 2; boolean f = ((x ^ y) < 0); // true int x = 3, y = 2; boolean f = ((x ^ y) < 0); // false
5.不用临时变量交换两个数
int a = 1, b = 2; a ^= b; b ^= a; a ^= b; // a = 2, b = 1
6.加一
1. int n = 1; 2. n = -~n; 3. // n = 2
7.减一
1. int n = 2; 2. n = ~-n; 3. // n = 1
ps:上面操作可以在小伙伴面前装杯用，其实没有啥实际用处.
3. 运用n&(n-1)
n &(n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1。
其核心逻辑就是，n - 1 一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和 n 做一次 & 运算，就可以仅仅把最后一个 1 变成 0 了。
下面用示例说明怎么用:
一题三解:二进制中1的个数
方法一:将整数n按位与1,即n&1,(按位与:结果都为1才为1),当n用二进制表示最右边为1时,则n&1为1，count++一次，然后将n向右移动>>一位依次比较.
直接上代码:
#include<stdio.h> int main() { int n; int ants = 0; scanf("%d",&n); for (int i = 0; i < 32; i++) { int m = n; if ((m>>i)&1== 1) ants++; } printf("%d", ants); return 0; }
方法二:和方法一大同小异,就是将整数n不动，向左移动1;这里就不提供代码了，感兴趣尝试尝试.
方法三:利用上面讲解的n&n(-1),这里不做详解，可以看上面
int hammingWeight(int n) { int res = 0; while (n != 0) { n = n & (n - 1); res++; } return res; }
判断一个数是不是2的指数
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
1. 2^0 = 1 = 0b0001 2. 2^1 = 2 = 0b0010 3. 2^2 = 4 = 0b0100
如果使用 n & (n-1) 的技巧就很简单了（注意运算符优先级，括号不可以省略）：
boolean isPowerOfTwo(int n) { if (n <= 0) return false; return (n & (n - 1)) == 0; }
牛刀小试
>>>2的指数(题目代码已在上面展示,如有问题可在评论区讨论)
4. 运用a^a=0
异或运算的性质是需要我们牢记的：
一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。
找出落单的数
对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素：
int singleNumber(int[] nums) { int res = 0; for (int n : nums) { res ^= n; } return res; }
牛刀小试
5. 位运算思维提升
将整数的奇偶位互换
这里的整数的奇偶位互换，实际上是二进制上奇偶位的互换。而不是十进制上的奇偶位互换，15，换成51。例如将1010换成0101;
思路:输入一个整数,让它按位与010101...保留偶数位的值记为ou(这句话需要品味)，然后再让它按位与101010...保留住奇数的值记为ji,然后将ou向左移<<一位,ji向右移动>>一位,然后再将其异或则会达成需要的目的.
代码:
#include<stdio.h> int main() { int n; scanf("%d",&n); int ji = n & 0xaaaaaaaa;//1010... int ou = n & 0x55555555;//0101... int c= (ou << 1) ^(ji >> 1); printf("%d",c); return 0; }
二进制表示浮点实数
代码:
0.625 0.5+0.125 0.101 #include<iostream> using namespace std; int main() { double n; cin >> n; string s1 = "0."; while (n > 0) { n= n * 2; if (n >=1) { s1 +="1"; n = n - 1; } else { s1 += "0"; n = n; } if (s1.size() > 34) { cout << "ERROR " << endl; } } cout << s1 << endl; return 0; }
出现K次与出现一次
解题的突破口：利用k个K进制的数进行不进位加法，结果是 0 的结论
先把十进制的数转为k进制，并采用字符串倒序存储
用除k取余法(通用的计算方法)，将数组中的数转为k进制数。
因为转化为k进制后要按位（列）进行计算，采用字符串的形式储存。转化为k进制后由于数的大小不同，长度也有可能不同，虽然对于有k个数的数字而言求和都是0没区别，但对要求的那个数来说位序很关键，（计算时是字符串是由左到右计算，而换算回十进制时是从右往左计算）所以要将转化为k进制的数倒序存储。
找出字符串的最大长度，然后对不足maxlen长度的字符串进行补齐
因为要一列一列地计算，所以要知道最多有多少列，即maxlen。在高位补“0”，补足maxlen长度，以便逐位做不进位加法
做不进位加法
将这些数进行不进位加法，相当于异或运算^，或者将按位相加后的数对k取模
输出结果，K进制转十进制
这步简单了，跟常见的八进制转十进制、十六进制转十进制一样的原理。
#include<iostream> #include<algorithm> #include<string> //#include<cmath> using namespace std; string decTok(int dec, int k); //十进制数转K进制 int kTodec(string str, int k); // K进制转十进制 string decTok(int dec, int k) { string ret = ""; //作为结果 while (dec > 0) { ret += char(dec%k + '0');//如：5+'0'='5' dec /= k; } reverse(ret.begin(), ret.end());//翻转 return ret; } int kTodec(string str, int k) { int ans = 0; for (int i = 0; i < str.size(); i++) ans = ans * k + (str[i] - '0');//020 首位是最高位 return ans; } int main() { int n[] = { 1,1,1,3,3,3,5,5,5,9,9,9,6,7,7,7 }; int k = 3; //根据数组数据，要转换的进制 //1.十进制数转K进制 string str[16]; for (int i = 0; i < 16; i++) str[i] = decTok(n[i], k); //2.找出16条字符串中最大长度 int maxlen = 0; int len; for (int i = 0; i < 16; i++) { len = str[i].size(); maxlen = max(maxlen, len); //maxlen=max(maxlen,str[i].size()) } //16条字符串中，若字符串长度<maxlen，则进行补齐，以便逐位做不进位加法 for (int i = 0; i < 16; i++) while (str[i].size() < maxlen) str[i] = "0" + str[i]; //ans:结果初始化 string ans = ""; while (ans.size() < maxlen) ans += "0"; //3.做不进位加法 for (int i = 0; i < 16; i++) for (int j = 0; j < maxlen; j++) ans[j] = char(((str[i][j] - '0') + (ans[j] - '0')) % k + '0'); cout << ans << endl; //ans字符串结果 cout<< kTodec(ans, k); //转为十进制数 return 0; }
