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

建议参考关于按位运算符的有趣事实作为前提条件。

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 that  has all 1's except the given position.
void unset( int &num, int pos)
{
     //Second step is to bitwise and this  number with given number
     num &= (~(1 <<pos));
}
int main()
{
     int num = 7;
     int  pos = 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;
}

输出如下：

2

竞争编程的位技巧

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。