竞争编程的按位技巧详细指南 _竞争编程

建议参考关于按位运算符的有趣事实作为前提条件。
1.如何设置数字" num"：
如果我们想在数字" num"中的第n个位置设置位, 可以使用" OR"运算符(|)完成。

首先, 我们通过(1 < < n)将" 1"移位到n位
然后, 使用" OR"运算符将位设置在该位置。使用" OR"运算符是因为即使先前未使用数字" num"的二进制表示来设置该位, 也会设置该位。

#include< iostream> using namespace std; //num is the number and pos is the position //at which we want to set the bit. void set( int & num, int pos) { //First step is shift '1', second //step is bitwise OR num |= (1 < < pos); } int main() { int num = 4, pos = 1; set(num, pos); cout < < ( int )(num) < < endl; return 0; }

输出如下：

6

我们已通过"通过引用致电"传递参数, 以永久更改号码。
2.如何取消/清除数字" num"中第n个位置的位：
假设我们想将数字" num"的第n个位置取消设置, 那么我们必须借助" AND"(＆)运算符来实现。

首先, 我们通过(1 < < n)将移位" 1"移至n位置, 而不是使用按位NOT运算符"?"取消设置此移位的" 1"。
现在, 清除此左移的" 1", 即使其变为" 0"后, 我们将对" AND"(＆)与数字" num"进行设置, 该数字将在第n个位置保留未设置的位。

#include < iostream> using namespace std; //First step is to get a number thathas all 1's except the given position. void unset( int & num, int pos) { //Second step is to bitwise and thisnumber with given number num & = (~(1 < < pos)); } int main() { int num = 7; intpos = 1; unset(num, pos); cout < < num < < endl; return 0; }

输出如下：

5

3.在第n个位置切换一点：
切换意味着如果先前将其设为``off''(0), 则将其设置为``on''(1), 如果先前将其设为``on''(1), 则将其设置为``off''(0)。我们将在此处使用``XOR''运算符是这个" ^"。 " XOR"运算符背后的原因是由于其属性。

" XOR"运算符的属性。
- 1 ^ 1 = 0
- 0 ^ 0 = 0
- 1 ^ 0 = 1
- 0 ^ 1 = 1
如果两位不同, 则" XOR"运算符将返回一个设置位(1), 否则将返回一个未设置的位(0)。

#include < iostream> using namespace std; //First step is to shift 1, Second step is to XOR with given number void toggle( int & num, int pos) { num ^= (1 < < pos); } int main() { int num = 4; int pos = 1; toggle(num, pos); cout < < num < < endl; return 0; }

输出如下：

6

4.检查第n个位置的位是否已设置或未设置：
使用" AND"运算符很容易做到。

左移" 1"到指定位置, 然后左移" AND"("＆")。

#include < iostream> using namespace std; bool at_position( int num, int pos) { bool bit = num & (1< < pos); return bit; }int main() { int num = 5; int pos = 0; bool bit = at_position(num, pos); cout < < bit < < endl; return 0; }

输出如下：

1

请注意, 我们首先左移了" 1", 然后使用" AND"运算符将其移到了该位置。因此, 如果" num"中" pos"位置的位置为" 1", 则在" AND"之后, 变量" bit"将存储" 1", 否则如果数字" num"中位置" pos"的位置为" 0"比"与"之后我们的变量位将存储" 0"。
一些更快速的技巧：

反转数字/ 1的补数的每一位：如果要反转数字的每一位, 即将位" 0"更改为" 1", 将位" 1"更改为" 0"。可以在"?"运算符的帮助下进行此操作。例如：如果数字为num = 00101100(二进制表示), 则"?num"将为" 11010011"。

【竞争编程的按位技巧详细指南】这也是" 1的数字补码"。

#include < iostream> using namespace std; int main() { int num = 4; //Inverting every bit of number num cout < < (~num); return 0; }

Output: -5

数字的两个补码：2的数字补数就是1的补数+ 1。

因此, 形式上我们可以找到2的补码, 方法是找到1的补码, 然后在结果中加1, 即(?num + 1), 否则我们可以做的就是使用"-"运算符。

#include < iostream> using namespace std; int main() { int num = 4; int twos_complement = -num; cout < < "This is two's complement " < < twos_complement < < endl; cout < < "This is also two's complement " < < (~num+1) < < endl; return 0; }

输出如下：

This is two's complement -4 This is also two's complement -4

剥离最低设置位：

在许多情况下, 我们想要剥离最低的设置位, 例如在Binary Indexed树数据结构中, 将一个设置位的数量计数。
我们做这样的事情：

X = X & (X-1)

但是它怎么工作？
让我们来看一个例子, 让X = 1100。
(X-1)会将所有位取反, 直到遇到最低位" 1", 并且还要反转最低位" 1"。
X-1变为1011。将X与X-1"与"后, 我们去除了最低的置位比特。

#include < iostream> using namespace std; void strip_last_set_bit( int & num) { num = num & (num-1); } int main() { int num = 7; strip_last_set_bit(num); cout < < num < < endl; return 0; }

输出如下：

6

获取数字的最低设置位：

这是通过使用表达式'X＆(-X)'完成的, 让我们看一个例子：让X =00101100。因此?X(1的补码)为'11010011', 2的补码为(?X + 1或-X), 即" 11010100"。因此, 如果我们将原始数字" X"与两个补码" -X"进行"与"运算, 则会得到最低的设置位。

00101100 & 11010100 ----------- 00000100

#include < iostream> using namespace std; int lowest_set_bit( int num) { int ret = num & (-num); return ret; } int main() { int num = 10; int ans = lowest_set_bit(num); cout < < ans < < endl; return 0; }

输出如下：