竞争性编程的位技巧
原文:https://www . geesforgeks . org/bit-ticks-competitive-programming/
在竞争性编程中，或者一般来说，有些问题看起来很难，但是可以用一点魔法很容易地解决。我们在前一篇文章中已经讨论了一些技巧。 【竞争编程的逐位黑客】 我们在本文中考虑了以下事实–
- 基于 0 的从右到左的位索引。
- 设置第 I 位意味着，将第 I 位变为 1
- 清除第 I 位意味着将第 I 位变为 0
1)清除从最低有效位到第一位的所有位T2】
mask = ~((1 << i+1 ) - 1);
x &= mask;
逻辑:要清除从 LSB 到第 I 位的所有位，我们必须在掩码为 LSB 到第 I 位 0 的情况下对 x 进行“与”。为了获得这样的掩模，首先向左移动 1 i 次。如果减去 1，从 0 到 i-1 的所有位都变成 1，剩下的位变成 0。现在我们可以简单地取掩码的补码，将所有第一个 I 位设为 0，剩余的设为 1。 示例- x = 29 (00011101)我们想要清除 LSB 到第 3 位，总共 4 位 掩码->1<<4->16(00010000) 掩码->16–1->15(00001111) 掩码->~掩码- > 11110000【
mask = (1 << i) - 1;
x &= mask;
逻辑:要清除从 MSB 到第 I 位的所有位，我们必须用具有 MSB 到第 I 位 0 的掩码对 x 进行“与”。为了获得这样的掩模，首先向左移动 1 i 次。如果减去 1，从 0 到 i-1 的所有位都变成 1，剩下的位变成 0。 示例- x = 215 (11010111)我们想要清除 MSB 到第 4 位，总共 4 位 掩码->116(00010000) 掩码->16–1->15(00001111) x&掩码->7(000001111)
x >>= 1;
逻辑:我们做算术右移时，每一位都向右移，空白位置用数字的符号位代替，正数为 0，负数为 1。由于每一位都是 2 的幂，每次移位，我们都将每一位的值减少 2 倍，这相当于 x 除以 2。 示例- x = 18(00010010) x>>1 = 9(00001001) 4)乘以 2
x <<= 1;
逻辑:我们做算术左移时，每一位都左移，空白位置用 0 代替。由于每一位都是 2 的幂，每次移位，我们都将每一位的值增加 2 倍，这相当于 x 乘以 2。 示例- x = 18(00010010) x<<1 = 36(00100100) 5)大写英文字母转小写
ch |= ' ';
逻辑:大写和小写英文字母的位表示为–
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010
如我们所见，如果我们设置第 5 位大写字符，它将被转换为小写字符。我们必须准备一个具有第 5 位 1 和其他 0 (00100000)的掩码。该掩码是空格字符(“”)的位表示。然后字符“ch”与掩码进行“或”运算。 示例- ch = ' A '(01000001) mask = ' '(00100000) ch | mask = ' A '(01100001) 详情请参考案例转换(下限到上限，反之亦然)。 6)小写英文字母改为大写
ch &= '_’ ;
逻辑:大写和小写英文字母的位表示为–
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010
如我们所见，如果我们清除第 5 位小写字符，它将被转换为大写字符。我们必须准备一个具有第 5 位 0 和其他 1 (11011111)的掩码。该掩码是下划线字符(“_”)的位表示。字符“ch”然后与面具。 示例- ch = ' A '(01100001) mask = ' _ '(11011111) ch&mask = ' A '(01000001) 详情请参考案例转换(下限到上限，反之亦然)。 7)计数整数中的设定位
卡片打印处理机（Card Print Processor 的缩写）
int countSetBits(int x)
{
int count = 0;
while (x)
{
x &= (x-1);
count++;
}
return count;
}
逻辑:这是 布莱恩·克尼根的算法。 8)查找 32 位整数的日志基数 2
卡片打印处理机（Card Print Processor 的缩写）
int log2(int x)
{
int res = 0;
while (x >>= 1)
res++;
return res;
}
逻辑:我们反复右移 x，直到它变成 0，同时我们继续计数移位操作。这个计数值是 log2(x)。 9)检查给定的 32 位整数是否为 2 的幂
卡片打印处理机（Card Print Processor 的缩写）
int isPowerof2(int x)
{
return (x && !(x & x-1));
}
逻辑:2 的所有幂只有一个位组，例如 16 (00010000)。如果我们减去 1，从 LSB 到置位位的所有位都会被切换，即 16-1 = 15 (00001111)。如果我们将 x 与(x-1)相加，结果是 0，那么我们可以说 x 是 2 的幂，否则不是。当 x = 0 时，我们必须格外小心。 示例 x = 16(00010000) x–1 = 15(00001111) x&(x-1)= 0 所以 16 是 2 的幂 更多位黑客请参考这篇文章。 本文由 阿图尔·库马尔 供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
