算法篇:位运算-爱代码爱编程
目录
文章最后编辑时间:2020-08-30 17:35
位运算
现代计算机中,几乎都是二进制计算机(三进制计算机仅有少量),所有的数据都以二进制的形式存储在设备中。
位运算就是直接对整数在内存中的二进制位进行操作。
常见的位运算
需要注意,位运算是针对 二进制 的运算,对每一个位进行布尔运算操作。所以 手动 进行 位运算计算 时,需要将数转换成二进制的表示形式,再进行计算。
1 按位与
只有对应位上两个都为1时,结果才得1,只要有一个为0,结果就是0,类似乘的关系。
2 按位或
对应位上有一个为1,结果就为1。两个都为0,结果才得0,类似加的关系。
3 按位取反
对每一位进行取反操作,如果是1则结果为0,是0则结果为1.
4 按位异或
当两个对应位不同时结果才为1,相同时得0.
5 按位同或
当两个对应位相同时结果才为1,不同时得0.
6 左移
将二进制位上的数向左移动,右边补0.
7 带符号右移
有符号整数最高位代表着数的正负,负数最高位为1。带符号右移是右移时,左边补充最高位上的值。负数右移,左边补1.
8 无符号右移
二进制上的数向右移动,右移时左边补0。
编程语言中的位运算
位运算主要有以下几种:
位运算 | C语言操作 | Java操作 |
---|---|---|
按位与 | a & b | a & b |
按位或 | a | b | a | b |
按位异或 | a ^ b | a ^ b |
按位取反 | ~a | ~a |
左移 | a << b | a << b |
带符号右移 | a >> b | a >> b |
无符号右移 | 无 | a >>> b |
嵌入式常用的位运算操作
BIT_N 表示 代表对应位的数,即 (1 << N)。
位的二进制形式输出
在C语言中,printf并不能直接以二进制的形式输出数,为了可以方便查看二进制位的值,编写如下函数,可以将某一个数转成不同进制的表示形式并输出。
任意进制的输出(2~36进制)
void printBase(unsigned int num, int nBit, int base)
{
char a[33] = "";
int n;
for (n = 0; num; num /= base) {
a[n++] = num % base;
}
for (int i = nBit - 1; i >= 0; i--) {
if (i >= n)
putchar('0');
else
(a[i] < 10) ? putchar(a[i] + '0') : putchar(a[i] + 'a' - 10);
if (i % 4 == 0)
putchar(' ');
}
}
二进制形式的输出
void printBin(unsigned int num, int nBit)
{
printBase(num, nBit, 2);
}
位置位
置位即将某一二进制位置为1
a = a | BIT_N;
简写为
a |= BIT_N;
对多位同时置为,可以将多个BIT_N位或
a |= (BIT_N1 | BIT_N2 | BIT_N3);
位清零
对某一位清零, 使用位与运算,对应位与0相与得0, 其它位与1相与不变。
对应位为0的码,使用BIT_N取反即可
a = a & (~BIT_N);
简写为
a &= ~BIT_N;
对多位同时清零,可以将多个BIT_N位或。
a &= ~(BIT_N1 | BIT_N2 | BIT_N3);
取a为1,b为0的位
即 a ⋅ b ˉ \ a \cdot \bar b a⋅bˉ, 如果取a为0, b 为1的位,交换a和b的位置即可。
c = a & (~b);
或者
c = (a ^ b) & a;
位逆序
常规逆序
- 新数左移,原数移出的位放入新数最低位,原数右移
- 复杂度为 N \ N N
long long bitReverse(unsigned int num, int N = 64)
{
unsigned int ans = 0;
while (N--) {
ans <<= 1;
ans |= ans & 1;
num >>= 1;
}
return ans;
}
蝴蝶算法
- 将一个二进制数上的N位逆序, 每次左右分半,进行交换
- 复杂度为 l o g N \ log N logN
- N = 8 的算法
data = (data<<4) | (data>>4);
data = ((data<<2) & 0xcc) | ((data>>2) & 0x33);
data = ((data<<1) & 0xaa) | ((data>>1) & 0x55);
- N位的蝴蝶算法(N为2的幂, int 是32位的,所以N 最大为32)
unsigned int bitReverse(unsigned int num, int N = 32)
{
int M = 16;
unsigned int mask = (unsigned int)(~0);
while (M) {
mask ^= mask >> M;
if (2 * M <= N)
num = ((num & mask) >> M) | ((num & ~mask) << M);
M >>= 1;
}
return num;
}
位循环移动
流水灯常常需要将某个端口的位循环移动, 端口通常为8位
- 循环移动N位
直接将左右进行交换,这是数组所不能的
void circleRightShift(unsigned char& port, int n) {
n %= 8;
port = (port >> n) | (port << (8 - n));
}
void circleLeftShift(unsigned char& port, int n) {
n %= 8;
port = (port << n) | (port >> (8 - N));
}
lowbit运算
l o w b i t lowbit lowbit 运算 是位运算中比较重要的运算方式。
lowbit概念
定义一个函数
f
=
l
o
w
b
i
t
(
x
)
f=lowbit(x)
f=lowbit(x),这个函数的值等于
x
x
x的二进制表达式中最低位的1所对应的值。
我们把数用二进制的形式来表示,如下(左为十进制数,右为二进制数)
:
(
2
)
10
=
(
10
)
2
(2)_{10} = (10)_{2}
(2)10=(10)2
(
5
)
10
=
(
101
)
2
(5)_{10} = (101)_{2}
(5)10=(101)2
(
24
)
10
=
(
11000
)
2
(24)_{10} = (11000)_{2}
(24)10=(11000)2
在上面 2, 5和24 的二进制表达式中,我们直接取最低位的1和后面的0,得到的值分别是
(
10
)
2
(10)_{2}
(10)2,
(
1
)
2
(1)_{2}
(1)2,
(
1000
)
2
(1000)_{2}
(1000)2,即 2, 1, 8,所以得到
l
o
w
b
i
t
(
2
)
=
(
10
)
2
=
2
lowbit(2) = (10)_{2} = 2
lowbit(2)=(10)2=2
l
o
w
b
i
t
(
5
)
=
(
1
)
2
=
1
lowbit(5) = (1)_{2} = 1
lowbit(5)=(1)2=1
l
o
w
b
i
t
(
24
)
=
(
1000
)
2
=
8
lowbit(24) = (1000)_{2} = 8
lowbit(24)=(1000)2=8
由上面的结果可以得出,假设一个数的二进制表示最低位的1在第
k
k
k位(从右往左,最右边为第0位)
,那么,这个数的
l
o
w
b
i
t
lowbit
lowbit值为
2
k
2^{k}
2k.
如下图,最低位1在第3位上,则
l
o
w
b
i
t
lowbit
lowbit 值为
2
3
=
8
2^3 = 8
23=8,也就是
(
1000
)
2
(1000)_2
(1000)2
lowbit运算的实现
得到一个数的
l
o
w
b
i
t
lowbit
lowbit值,即取出一个数的最低位,可通过如下操作:
假设原来的数是a,对a进行取反就得到b,b再加1得到c,最后原数a和c进行位与操作,就得到了
l
o
w
b
i
t
lowbit
lowbit值。
所以求
l
o
w
b
i
t
lowbit
lowbit值的运算方法为:
lowbit = n & (~n + 1);
因为取反加1就是一个数的负数的补码,所以也写作
lowbit = n & (-n);
当这个数是0,没有最低位1的时候,结果为0。
消去lowbit
一个数消去它的 l o w b i t lowbit lowbit 位,由上面的 l o w b i t lowbit lowbit 求法,直接减去它的 l o w b i t lowbit lowbit值 即可
n -= n & (-n);
还可以由 n 和 (n-1)位与 得到:
n &= (n-1);
通过不断进行消除 l o w b i t lowbit lowbit 操作,最后会变成0,并且 0 & (0-1) = 0,不会有变化。
求一个二进制数所包含的1的个数
这个就是不断进行消除
l
o
w
b
i
t
lowbit
lowbit 操作,记录变成0所需要的操作次数即可。
因为是计算二进制的位数,所以参数为无符号整数。
int calcNumOfBit1(unsigned int n)
{
int count = 0;
while (n != 0) {
n &= (n-1);
++count;
}
return count;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_39151563/article/details/108305105