我不知道如何在x的二进制形式中将任何连续的1变为0(连续的1意味着包含多个1的1的集合)。
问题规格:允许的操作员:!~ & ^|+ << >>(无循环或其他控制结构)最大运算符数量:16
示例
- cleanConcretive1(0x10)= 0x10
- cleanConcretive1(0xF0)= 0x0
- cleanConcretive1(0xFFFF0001)= 0x1
- cleanConcretive1(0x4F4F4F4F)= 0x40404040
这是我目前为止所尝试的
int cleanConsecutive1(int x) {
x = (x | (x >> 1)) & ~(x & (x >> 1));
x = (x | (x >> 2)) & ~(x & (x >> 2));
x = (x | (x >> 4)) & ~(x & (x >> 4));
x = (x | (x >> 8)) & ~(x & (x >> 8));
return x;
}
3条答案
按热度按时间nfeuvbwi1#
可以按如下方式完成:
输出量:
其思想是首先屏蔽除了未置位右边的那些位之外的偏移置位,然后屏蔽除了未置位左边的那些位之外的偏移置位。因此,结果中仅保留在左和右具有未置位的置位位。
在此上下文中,在输入的两端存在虚构的未置位位。这些是我们必须在掩码中通过
|
设置的位。我已经将函数改为使用
unsigned
而不是有符号的int
,因为对于负值,移位运算符没有很好的定义。6ojccjat2#
五次手术:
x & ~(x << 1 | x >> 1)
。将
x
左移一位和右移一位,并对它们进行OR运算,得到一个掩码,如果x
中有1与之相邻,则每个位都被设置。然后又道:x
中的任何孤立的1都没有与之相邻的1,因此掩码中的该位置处有0。然后,掩码用于关闭
x
中的位,方法是将其与x
进行求补和AND运算。如上所述,这将关闭每个1位,该位具有相邻的1。x
应该是无符号的或比int
窄,以避免符号位的问题。9rbhqvlz3#
我在给定的GPT代码中识别出的一个小习惯用法是
x&(x>>1)
将连续的1捕获到掩码中,然后使用not
和and
清除它们上面的代码片段会在每次运行中将连续的1减少到最高位,并清除其余部分。
我们能把它们降到最低位吗?当然可以:
我们正在清除比特,因此我们可以将两者合并结合起来:
似乎工作。