程序地带

位运算进阶


目录编码光速大整数乘法二进制状态压缩位运算操作运算符优先级$lowbit$ 计算推导Code内置函数参考文献


编码

在 m 位二进制数中,通常称最低位为 0 位,从右到左以此类推,最高位为 (m-1) 位。


当无符号整数 (unsigned) 爆了的时候,它会自动 %,不会爆出负数。


C++ 的十六进制常常以 “0x” 开头,“0x” 后面的部分对应具体的十六进制的数值。当使用 memset 时,memset 只能赋值出 “每 8 位都相同的数”。当需要把一个数组中的数值初始化为正无穷时,为了避免加法算术上溢出或者繁琐的判断,我们经常用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3F 3F 3F 3F 的值来代替。


对于数字 0x3F 3F 3F 3F,它是满足以下两个条件的最大整数:


整数的两倍不超过 0x7F 7F 7F 7F,即 int 能表示的最大正整数。
整数的每 8 位(每个字节) 都是相同的。
光速大整数乘法

时间复杂度为 (O(1))


ull mul(ull a,ull b,ull p)
{
a%=p;
b%=p;
ull c=(long double) a*b/p;
ull x=a*b;
ull y=c*p;
ll ans=(ll)(x%p)-(ll)(y%p);
if(ans<0) ans+=p;
return ans;
}

时间复杂度为 (O(log_2b))


ll mul(ll a,ll b,ll p)
{
ll ans=0;
for(;b;b>>=1)
{
if(b&1) ans=(ans+1)%p;
a=a*2%p;
}
return ans;
}
二进制状态压缩
位运算操作

二进制状态压缩,是指将一个长度为 m 的 bool 数组用一个 m 位二进制整数表示并存储的方法。利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。


操作
运算
取出 n 的第 k 位
( n >> k ) & 1
取出 n 的后 k 位( 0 ~ k-1 位)
n & ( ( 1 << k ) - 1 )
将第 k 位取反,赋值到 n
n = n xor ( 1 << k )
将第 k 位变为 1,赋值到 n
n |= ( 1 << k )
将第 k 位变为 0,赋值到 n
n &= ( ~ ( 1 << k ) )

这种方法运算简便,比暴力从十进制算出二进制的每一位节省了大量的时间和空间。


推荐题目:CSP-S2020 动物园


运算符优先级

从高到低排列:


加减
移位
比较大小
按位与
按位异或
按位或
+ , -
<< , >>
> , < , == , !=
&
xor ( C++ ^ )
|

如果不确定优先级,则可以加一些括号,以保证运算顺序的正确性。

(lowbit) 计算

lowbit(n) 定义为非负整数 n 在二进制表示下 “最低位的 1 及其后边所有的 0 构成的数值”。

推导

设 (n>0) ,(n) 的第 (k) 位是 (1),第 (0) ~ (k-1) 位都是 (0)。

为了实现 lowbit 运算,先把 (n) 取反,此时第 (k) 位变为 0, 第 (0) ~ (k-1) 位都是 1。再令 (n=n+1) ,此时因为要进位,第 k 位变为 1 ,第 (0) ~ (k-1) 位都是 0。

在上面的取反加 1 操作后,(n) 的第 (k+1) 到最高位恰好与原来相反,所以 (n ~& ~(sim n+1)) 仅有第 (k) 位为 1,其余位都是 0。而在补码表示下,(sim n = -1-n),因此:

[lowbit(n)=n ~& ~(sim n+1) = n ~& ~(-n)
]

Code

配合 Hash 代替 (log) 运算,可以使复杂度降低。

const maxn = 1 << 20;
int H[maxn];
for(int i=0; i<=20; ++i)
H[1 << i] = i; //预处理
while(cin >> n) //对多组数据进行求解
{
while(n > 0)
{
cout << H[n & -n] << " ";
n -= n & -n;
}
puts("");
}
内置函数

下面这些仙术可以高效计算 lowbit 以及二进制中 1 的个数。但是,部分竞赛禁止 使用下划线开头的库函数,所以这些内置函数在竞赛里不要使用。


返回 (x) 的二进制表示下最低位的 1 后面有多少个 0:
int __builtin_ctz (unsigned int x)
long long __builtin_ctzll (unsigned long long x)


返回 (x) 的二进制表示下有多少位为 1:
int __builtin_popcount (unsigned int x)
int __builtin_popcountll (unsigned long long x)


参考文献

李煜东 《算法竞赛 进阶指南》

EdisonBa

2021.1.15


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/EdisonBa/p/14281177.html

随机推荐

三地五中心(2)

上篇文章我们总结了一下同城双活、异地多活、两地三中心等一些部署架构,那么这篇文章我来发表一下我对三地五中心的理解。我们上篇文章讲过两地三中心这个架构,如下图:...

这瓜保熟么 阅读(772)

vim 格式化代码,使代码变得整齐

1.左右括号没有对齐,代码行东一个西一个,强迫症表示很不爽2.vim如何解决把光标停留在需要格式化的代码末尾先按Esc,再按v,进入可视化阶段使...

研究猿小刘 阅读(161)

强大的lambda语法

看懂lambdajavalambda有能力表达一个完整的方法签名(带返回值),但在开发中总是写全lambda并不能达到简化代码的效果,因此开发中我们更愿意使用lambda简...

FYHannnnnn 阅读(810)

Maya2020使用经验总结-01

Maya2020使用经验总结-01前言:因工作需要,半道学习maya,0基础,没有系统的知识,所以把自己的一些常见问题集中写在这里...

爻清 阅读(293)

word2vec过程

word2vec实现过程实战实现过程先有大量文本,构成txt文档;利用分词工具对文本进行分词;分词后的结构用word2vec来进行训练,无监督训...

xiaoxiaoqian0519 阅读(330)

Linux常用命令(2)---增、删、改、查

Linux常用命令(2)---增删改查一、alias——设置别名二、du——统计目录及文件空间占用情况三、mkdir——创建新目录四、touch——创建空文件五、ln——创...

狗子说不熬夜不开心 阅读(141)