竞争性编程的小技巧-yiteyi-C++库

在竞争性编程或一般情况下，有些问题似乎很难解决，但可以很容易地用一点点魔法解决。我们在之前的帖子下面讨论了一些技巧。竞争性编程的逐位黑客我们在本文中考虑了以下事实——

null

从右到左的基于0的位索引。
设置第i位意味着将第i位设置为1
清除第i位意味着将第i位变为0

1）清除LSB到第i位的所有位

mask = ~((1 << i+1 ) - 1);
x &= mask;

逻辑： 要清除从LSB到第i位的所有位，我们必须使用LSB到第i位0的掩码和x。要获得这样的口罩，首先左移1 i次。如果我们从中减去1，从0到i-1的所有位都变成1，剩下的位变成0。现在，我们可以简单地利用掩码的补码，将所有的第一个i位设置为0，剩余的i位设置为1。范例- x=29（00011101），我们想将LSB清除到第三位，总共4位面具->1<<4->16（00010000）面罩->16–1->15（00001111）面具->面具->11110000 x&mask->16（00010000） 2）清除从MSB到第i位的所有位

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位面具->1<<4->16（00010000）面罩->16–1->15（00001111） x&mask->7（00000111） 3）除以2

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（00100） 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）掩码=“”（00100000） ch | mask=’a’（0110001）请参考大小写转换（从低到高，反之亦然）详细信息。 6）从小写字母到大写字母

ch &= '_’ ;

逻辑： 大写和小写英文字母的位表示为——

A -> 01000001                a -> 01100001
B -> 01000010                b -> 01100010
C -> 01000011                c -> 01100011
.                               .
.                               .
Z -> 01011010                z -> 01111010

我们可以看到，如果清除第5位的小写字符，它将被转换为大写字符。我们必须准备一个有第5位0和其他1（11011111）的掩码。此掩码是下划线字符（“u1”）的位表示形式。然后是带有面具的角色“ch”。范例- ch=‘a’（0110001）掩码=’u511;’（11011111） ch&mask=’A’（01000001）请参考大小写转换（从低到高，反之亦然）详细信息。 7）以整数计算设置位

CPP

                             int                                           countSetBits(                                           int                                           x)                           
                             {                           
                                                         int                                           count = 0;                           
                                                         while                                           (x)                           
                                                         {                           
                                                         x &= (x-1);                           
                                                         count++;                           
                                                         }                           
                                                         return                                           count;                           
                             }                           

逻辑： 这是 布莱恩·克尼根的 算法 . 8）查找32位整数的日志基数2

CPP

                             int                                           log2(                                           int                                           x)                           
                             {                           
                                                         int                                           res = 0;                           
                                                         while                                           (x >>= 1)                           
                                                         res++;                           
                                                         return                                           res;                           
                             }                           

逻辑： 我们反复右移x，直到它变为0，同时我们继续计算移位操作。这个计数值是log2（x）。 9）检查给定的32位整数是否为2的幂

CPP

int isPowerof2( int x)

{

return (x && !(x & x-1));

}

逻辑： 2的所有幂只有一个位设置，例如16（00010000）。如果我们从中减去1，那么从LSB到set bit的所有位都被切换，即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的幂请参考这更多比特黑客文章。本文由 阿图尔·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章