有意思的操作

基本操作

位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：“∧” 按位异或（取不同）、“&” 按位与（取交）、“|” 按位或（取并）、“~” 取反、“<<” 算术左移和 “>>” 算术右移。

  • n & (n - 1) 可以去除 n 的位级表示中最低的那一位，例如对于二进制表示 11110100 ，减去 1 得到 11110011，这两个数按位与得到 11110000。
  • n & (-n) 可以得到 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，取负得到 00001100，这两个数按位与得到 00000100。

获取二进制数中1的个数

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int bitset_contains(u32 s,int i)
{
    if(((s>>i) & 0x01) == 1) return 1;
    else return 0;
}

int bitset_size0(u32 s)
{
    int n;
    for(int i=0; i<32; i++)
    {
        n += bitset_contains(s,i);
    }
    return n;
}

int bitset_contains(u32 s,int i)就是判断s的第i位（从第0位开始计起）是否为1。

int bitset_size0(u32 s)就是一位位看是不是1，是就计数加一。

最后效果就是统计s为1的位数

方法二

1
2
3
4
5
6
7
8
9
int bitset_size(u32 s)
{
    s = (s & 0x55555555) + ((s>>1) & 0x55555555); //01010101010101010101010101010101
    s = (s & 0x33333333) + ((s>>2) & 0x33333333); //00110011001100110011001100110011
    s = (s & 0x0f0f0f0f) + ((s>>4) & 0x0f0f0f0f); //00001111000011110000111100001111
    s = (s & 0x00ff00ff) + ((s>>8) & 0x00ff00ff); //00000000111111110000000011111111
    s = (s & 0x0000ffff) + ((s>>16) & 0x0000ffff);//00000000000000001111111111111111
    return s;
}

​ 一般来说，看到这样的十六进制数就会不由自主地想把它们转换为二进制看看。转换之后呢就能稍微看出一些端倪了。😁

​ 0x55555555将s分为两个一组，每一组两位数。其实就是==分别判断一组里的两位数是不是1==。

  • 都是1，则变为1+1=10；
  • 只有一个，就变为01；
  • 没有则为0

​ 变换完了之后呢，储存的就是这一组里 “1” 的个数。

​ 0x33333333则是将s分为四个一组，一组里同样是两个数，只不过一个数是两位。操作的结果呢就是将两个数各自两个位里1的个数加起来，即四个位里1的个数。

​ 0x0f0f0f0f将s分为八个一组，统计八个位里1的个数

​ 0x00ff00ff将s分为十六个一组，统计十六位里1的个数

​ 0x0000ffff将整个32位的s看作一组，统计所有1的个数

比较

​ 两种方法比较来看，明显是第一种方法简单易懂，也容易想到；但是从运算效率上来看，第二种远远高于第一种。

遥控数据解析

遥控协议.png

1
2
3
4
5
6
7
8
9
10
void RemoteReceive(volatile uint8_t *const ptr_sbus_rx_buffer)
{
    if(ptr_sbus_rx_buffer == NULL) return;
    RC_Ctl.rc.ch0 = (ptr_sbus_rx_buffer[0] | (ptr_sbus_rx_buffer[1] << 8)) &0x07ff;
    RC_Ctl.rc.ch1 = (ptr_sbus_rx_buffer[1] >> 3) | (ptr_sbus_rx_buffer[2] << 5) & 0x07ff;
    RC_Ctl.rc.ch2 = (ptr_sbus_rx_buffer[2] >> 6) | (ptr_sbus_rx_buffer[3] << 2) | (ptr_sbus_rx_buffer[4] << 10) & 0x07ff;
    RC_Ctl.rc.ch3 = (ptr_sbus_rx_buffer[4] >> 1) | (ptr_sbus_rx_buffer[5] << 7) & 0x07ff; 
    RC_Ctl.rc.s1 = (ptr_sbus_rx_buffer[5] >> 6) & 0x0003;
    RC_Ctl.rc.s2 = (ptr_sbus_rx_buffer[5] >> 4) & 0x0003;
}

概括来说就是依照通信协议利用位移运算和或、与运算，将数据从ptr_sbus_rx_buffer剥离提取至RC_Ctl.rc.xx中。

  • 位移操作后，需要提取的数据在后11位(或后2位)，0x07ff换成二进制就是0000011111111111，过滤掉不需要的位数；0x0003同理
  • ch0获取buffer[0]全部八位和buffer[1]低三位
  • ch1获取buffer[1]高五位和buffer[2]低六位
  • ch2获取buffer[2]高两位和buffer[3]全部八位和buffer[4]低一位
  • ch3获取buffer[4]高七位和buffer[5]低四位
  • s1获取buffer[5]高两位
  • s2获取buffer[5]第五第六位

不知道是不是搞反了，根据协议来看是s1获取buffer[5]第五第六位，s2获取buffer[5]高两位

位运算实现四则运算

加法

算法思路

​ 在平时手算的时候我们经常会列竖式，先不考虑进位，只看和和相加的两个数同位的数，把进位数写小一点记在横线上方。计算下一位的时候再加上上一位的进位。

​ 所以在程序中也是模拟这样一个思路：

  • 先不看进位，得到一个和；记下进位
  • 进位在与和相加，不看进位得到一个新的和；同时也得到新的进位
  • 不断迭代递推，直到不再产生新的进位

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @brief 加法函数
 * @param ini_x 加数1
 * @param ini_y 加数2
 * @return 补码形式的结果
 */
u32 addition(u32 ini_x, u32 ini_y)
{
    //不需要转换为补码
    u32 x = ini_x, y = ini_y;
    //和，进位
    u32 ans,carry;
    ans = x ^ y;
    carry = (x & y) << 1;
    //不断获取进位与不考虑进位的和，迭代相加，直至进位为0
    while(carry != 0)
    {
        u32 i = ans, j = carry;
        ans = i ^ j;
        carry = (i & j) << 1;  
    }
    //DEBUG调试
    //printf("DEBUG: %d add %d = %d\r\n",ini_x,ini_y,ans);
    return ans;
}

​ 可以发现，

  • 不看进位得到的和其实就是两数异或，即ans = x ^ y;；
  • 进位即两数相与再左移一位，即carry = (x & y) << 1;

减法

​ a-b 即 a+(-b)

乘法

算法思路

​ 可以将被乘数不断加乘数次数的自己。但是这样效率不高。同样是模拟手算的思想，从乘数的最低位到最高位，在第i位，即给最后乘积贡献的值为

==被乘数 乘数[i] (进制数)^(i-1)^==

​ 在这个算法下不再能直接用补码参与计算，所以要换成原码并去除符号位。在开始的时候根据两数记下乘积的正负值，计算完毕之后再赋回去。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @brief 乘法
 * @param ini_x 
 * @param ini_y 
 * @return u32 积
 */
u32 multiplication(u32 ini_x, u32 ini_y)
{
    bool negative_flag=0;
    u32 ans=0, x=ini_x, y=ini_y;
    //判断积正负
    if( ( (x&0x80000000) && !(y&0x80000000) )||( !(x&0x80000000) && (y&0x80000000) ) ) {negative_flag=1;}
    //要转换为原码并去掉符号位
    x = back_com(x);
    y = back_com(y);
    x &= 0x7fffffff;
    y &= 0x7fffffff;
    //借鉴竖乘法
    for(int i=1;i<=31;i++)
    {
        if(y&0x01) {ans = addition(ans,x);}
        y = y>>1;
        x = x<<1;
        if(y == 0) {break;}
    }
    //加上正负号
    if (negative_flag) 
    {
        ans |= 0x80000000;//这个时候依然是原码，想直接用%d，要转换为补码
        ans = get_com(ans);
    }
    //DEBUG调试
    //printf("DEBUG: %d multiply %d = %d\r\n",ini_x,ini_y,ans);
    return ans;
}

除法

​ 因为除法有商和余数，所以用了一个结构体方便存储。

1
2
3
4
5
6
7
8
9
/**
 * @brief 除法答案结构体
 * @param ans 商
 * @param mod 余数
 */
typedef struct __ans_division_t{
    u32 ans;
    u32 mod;
}ans_division_t;

算法思路

​ 也是模拟手算流程，在理解了乘法的实现思路后便很容易理解。

  • 将被除数不断进位，即乘上进制数，直到恰好比被除数小。
  • 用被除数除以进位后的除数得到商（为了区别最终的商把它叫做小商吧），同时商加上==小商*进制数^(进位次数)^==
  • 被除数不断退位（除以进制数），同时重复上述操作，直到回到最初大小，即进位数为0

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @brief 除法
 * @param ini_x 被除数
 * @param ini_y 除数
 * @return ans_division_t* 答案指针
 */
ans_division_t *division(u32 ini_x, u32 ini_y)
{
    bool negative_flag=0;
    u32 ans=0, carry=0, x=ini_x, y=ini_y;
    ans_division_t *ans_division;
    ans_division = (ans_division_t*)malloc(sizeof(ans_division_t));
    if( ( (x&0x80000000) && !(y&0x80000000) )||( !(x&0x80000000) && (y&0x80000000) ) ) {negative_flag=1;}
    //要转换为原码并去掉符号位
    x = back_com(x);
    y = back_com(y);
    x &= 0x7fffffff;
    y &= 0x7fffffff;
    //依然是模拟手除流程
    //除数不断进位直至比被除数大
    while(y < x) 
    {
        y = y<<1;
        carry = addition(carry,1);
    }
    //如果能除，商就加上1<<carry，除数再不断右移直至回到本来大小。
    while(carry)
    {
        if(x>=y)
        {
            ans = addition(ans,1<<carry);
            x = addition(x,-y);
        }
        y = y>>1;
        carry = addition(carry,-1);
    }
    if(x>=y) 
    {
        ans = addition(ans,1);
        x = addition(x,-y);
    }
    //赋值
    ans_division->ans = ans;
    ans_division->mod = x;
    return ans_division;
}

​ 因为负数的余数比较奇怪，平时也不用，这里没有考虑在内。

DEBUG

​ vscode 程序文件不能用中文命名。

​ 在程序运行的时候使用补码记录。即便是usigned int，倘若scanf -9，对应二进制编码也是11111111111111111111111111110111。int型同样如此。

​ 所以在运算的时候不需要人为的去转换为补码了，在这方面耽误了不少时间。

​ 而对于同样的一串二进制编码，printf(“%d”)和printf(“%u”)输出结果是不一样的：%d会自动转换输出原码对应的有符号数；那%u则是会将这个补码当作原码直接换算成十进制输出。

存储形式·1.png

存储形式2.png

​ 其余的就是一些逻辑漏洞了，不得不说VScode写代码还是比Keil舒服😁

有关位运算的一些有意思的题目

只出现一次的数字

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

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

示例 1:

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

示例 2:

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

思路

需要用到异或运算的性质：

a \^ a = 0
a \^ 0 = a
a \^ b \^ a = b \^ (a \^ a) = b（交换律和结合律）
所以只要全部异或最后结果就是答案

代码实现

1
2
3
4
5
6
int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (const int & num: nums)
        ans ^= num;
    return ans;
}

比特位计数

给定一个非负整数 n，求从 0 到 n 的所有数字的二进制表达中，分别有多少个 1。

思路

本题可以利用动态规划和位运算进行快速的求解。定义一个数组 dp，其中 dp [i] 表示数字 i 的二进制含有 1 的个数。对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数 则为 dp [i-1] + 1；如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即 dp [i>>1]。

代码实现

1
2
3
4
5
6
7
vector<int> countBits(int num) {
    vector<int> dp(num+1, 0);
    for (int i = 1; i <= num; ++i)
        dp[i] = i & 1? dp[i-1] + 1: dp[i>>1];	
    // 等价于dp[i] = dp[i&(i-1)] + 1;
    return dp;
}