算法竞赛中位运算的运用

基础应用

符号名称运算规则
&两个位都为1时,结果才为1
|两个位都为0时,结果才为0
^异或两个位相同为0,相异为1
~取反0变1,1变0
<<左移各二进位全部左移若干位,高位丢弃,低位补0
>>右移各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

1.判断奇偶数

使其和1做与运算

int n=x&1;
//如果n=1,那么这个数是奇数,如果n=0,那么这个数为偶数

如果你对原理不感兴趣只想记结论的话那么请跳过这段内容。


在解释这个之前我们先来学习一下源码,反码,补码的知识。

机器数:一个数在计算机中的二进制表示形式。带符号,在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

十进制中的数 +5 ,计算机字长为8位,转换成二进制就是00000101。
如果是 -5 ,就是 10000101 。

真值:因为第一位是符号位,所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000101,其最高位1代表负,其真正数值是 -5 而不是形式值133(10000101转换成十进制等于133)。所以,为区别,将带符号位的机器数对应的真正数值称为机器数的真值。

0000 0001的真值 = +000 0001 = +1
1000 0001的真值 = –000 0001 = –1。

原码:符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值

[+1]原 = 0000 0001
[-1]原 = 1000 0001
//因为第一位是符号位, 所以8位二进制数的取值范围是:[1111 1111 , 0111 1111],即为[-127 , 127]

反码:正数的反码是其本身,负数的反码是在其原码的基础上, 符号位不变,其余各个位取反.

[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反

补码:正数的补码是其本身,负数的补码在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

理解了上面的内容之后,原理也就显而易见了。因为奇数的二进制最低为必然是1,偶数的二进制最低位必然是0,而1的8位二进制数表示为00000001,奇数与其做与运算结果必然为00000001(十进制1),偶数与其做与运算结果必然为00000000(十进制0)

2(BIN:0000 0010)&1(BIN:0000 0001)=0(BIN:0000 0000)
3(BIN:0000 0011)&1(BIN:0000 0001)=1(BIN:0000 0001)

2.获取某个二进制位是1还是0

N:待判断的二进制数
B:待判断的位(右往左)
结果:((N>>(B-1))&1
将要判断的为左移到最低位,然后让其和1做与运算即可。

骚操作

1.找到数组中唯一成对的那个数


原理:A^A=0,0^B=B
所以对于一个整数序列[A,A,B,B,C],有A^A^B^B^C=0^C=C,所以对于本题目,再构造一个数组包含1-1000这1000个数(这样原本成对的那个数变为3个,其他数变为2个),与原来的数组做累异或操作,最后所得结果即为答案。
代码实现:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> nums;
    for (int i = 1; i <=1000; i++)
    {
        nums.push_back(i);//构造数组
    }
    for (int i = 1; i <= 1000; i++)
    {
        nums.push_back(i);//构造数组
    }
    nums.push_back(123);//添加重复的数字
    int re = 0;
    for (int i = 0; i < nums.size();i++)
    {
        re ^= nums[i];
    }
    cout << re;
    return 0;
}

2.计算二进制中1的个数

常规思路:将这个数逐位右移再与1做与运算,计数。
骚操作之预备知识:二进制N和N-1的关系

0001 0000-1=0000 1111//一个二进制数减1即为将位数最低的1变为0,这位之后的位数变为1
0000 0101-1=0000 0100
0010 0100-1=0010 0011

观察一下0010 0100和该数减去1之后的结果0010 0011,倘若我们对其做与运算,其结果为0010 0000。
如果我们再次重复上面的步骤
0010 0000&(0010 0000-1)
其结果就变为了0(BIN:0000 0000)
所以,我们便可以根据这条性质对一个二进制数中的1的数量进行计数。
代码实现:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int bin = 30;//(BIN:0001 1110) 1的数量为4个;
    int T = 0;
    while (bin & (bin - 1))
    {
        bin = bin & (bin - 1);
        T++;
    }
    cout << ++T;//因为当bin=0时的那次并没有计算,所以要加一
    return 0;
}

运行结果:

3.用一条语句判断一个整数是不是2整数次方

原理:二的整数次方的二进制位中有且只有1个1
代码实现:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    P:
    int bin;
    cin >> bin;
    if ((bin & (bin - 1))== 0)
    {
        cout << "该整数是2整数次方"<<endl;
    }
    else
    {
        cout << "该整数不是2整数次方"<<endl;
    }
    goto P;
    return 0;
}

运行结果

4.将整数的奇偶位互换

有一个二进制数BIN:0000 0101我们想让其奇数位和偶数位互相交换(交换结果为0000 1010)
常规思路:我们将其逐个右移取出,放入一个字符数组中,然后在迭代依次交换;
骚操作原理

对于一个二进制数1101 0110,
首先,让其和0xaaaaaaaa(即1010 1010 1010 1010 1010 1010 1010 1010)//这里用16进制数aaaaaaaa表示32位二进制数(一位16进制数可以代表4位2进制数)做与运算,目的在于取出偶数位。
结果为A:1000 0010
再让原数和0x55555555做与运算(即0101 0101 0101 0101 0101 0101 0101 0101)//这里用16进制数aaaaaaaa表示32位二进制数(一位16进制数可以代表4位2进制数)做与运算,目的在于取出奇数位。
结果为B:0101 0100
将A右移一位:0100 0001
将B左移一位:1010 1000
将A和B做异或运算:1110 1001
到此,我们便成功交换了原数中的奇数位和偶数位。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int bin = 0b00000000000000000000000000001001;//要交换的数。BIN:0000 0000 0000 0000 0000 0000 0000 1001,DEC:9
    int os =bin&0xaaaaaaaa;//BIN:1010 1010 1010 1010 1010 1010 1010 1010‬
    int js = bin&0x55555555;//BIN:‭0101 0101 0101 0101 0101 0101 0101 0101‬
    //该语法由GCC编译器实现,并非C++语法 
    int shouldbe = 0b00000000000000000000000000000110;//预期值,BIN:0000 0001 0111 1110 0000 1010 0101 0110,DEC:6
    int answer =(os>> 1) ^ (js << 1);
    if (answer == shouldbe)cout << "yes";
    else cout << "no ";
    return 0;
}

运行结果

5. 0~1间浮点数的二进制表示

对于一个0-1间的浮点数0.625,转化为二进制的步骤为:

乘以2 -->1.25如果整数部分大于1,在其二进制表示0.后添加1.否则添加0
0.1
将整数部分变为0 -->0.25
只要不为0,重复以上步骤


乘以2 -->0.5,如果整数部分大于1,如果整数部分大于1,在其二进制表示0.1后添加1.否则添加0
0.10
将整数部分变为0 -->0.5
只要不为0,重复以上步骤


乘以2 -->1.0,如果整数部分大于1,如果整数部分大于1,在其二进制表示0.10后添加1.否则添加0

0.101
将整数部分变为0 -->0.0
此时已经为0,结束。
所以,0.625的二进制表示为0.101

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    double num;
    cin >> num;
    string bin="0." ;
    while (num != 0)
    {
        num*=2;
        if (num >= 1)
        {
            bin += '1';
        }
        else
        {
            bin +='0';
        }
        int temp = num;
        num -= temp;
        
    }
    if (bin.size() > 34)cout << "不能用32位二进制表示";
    else cout << bin;
    return 0;
}

运行结果


知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

Last modification:May 29th, 2019 at 04:01 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment