如何在C中将二进制形式的1变为零

xkrw2x1b  于 2023-10-16  发布在  其他
关注(0)|答案(3)|浏览(261)

我不知道如何在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;
}
nfeuvbwi

nfeuvbwi1#

可以按如下方式完成:

#include <stdio.h>

unsigned cleanConsecutive1(unsigned x) {
    return x & ((~x >> 1) | ~(~(0u) >> 1)) & ((~x << 1) | 1);
    // Multi-line version:
    //   unsigned msb = ~(~(0u) >> 1);
    //   unsigned left_mask = (~x >> 1) | msb;
    //   unsigned right_mask = (~x << 1) | 1;
    //   return (x & left_mask & right_mask);
}

#define TEST(x) printf("0x%08x -> 0x%08x\n", x, cleanConsecutive1(x))

int main()
{
    TEST(0x10);
    TEST(0xF0);
    TEST(0xFFFF0001);
    TEST(0x4F4F4F4F);
}

输出量:

0x00000010 -> 0x00000010
0x000000f0 -> 0x00000000
0xffff0001 -> 0x00000001
0x4f4f4f4f -> 0x40404040

其思想是首先屏蔽除了未置位右边的那些位之外的偏移置位,然后屏蔽除了未置位左边的那些位之外的偏移置位。因此,结果中仅保留在左和右具有未置位的置位位。
在此上下文中,在输入的两端存在虚构的未置位位。这些是我们必须在掩码中通过|设置的位。
我已经将函数改为使用unsigned而不是有符号的int,因为对于负值,移位运算符没有很好的定义。

6ojccjat

6ojccjat2#

五次手术:x & ~(x << 1 | x >> 1)
x左移一位和右移一位,并对它们进行OR运算,得到一个掩码,如果x中有1与之相邻,则每个位都被设置。然后又道:

  • x中的任何孤立的1都没有与之相邻的1,因此掩码中的该位置处有0。
  • 组中的任何1都有一个1与之相邻,因此掩码中的该位置处有一个1。
  • 一个0可能有也可能没有一个1与之相邻,但我们不关心掩码中的那个位置是什么,因为0或1都可以与下面的一起工作。

然后,掩码用于关闭x中的位,方法是将其与x进行求补和AND运算。如上所述,这将关闭每个1位,该位具有相邻的1。
x应该是无符号的或比int窄,以避免符号位的问题。

9rbhqvlz

9rbhqvlz3#

我在给定的GPT代码中识别出的一个小习惯用法是

x & ~(x & (x >> 1))

x&(x>>1)将连续的1捕获到掩码中,然后使用notand清除它们
上面的代码片段会在每次运行中将连续的1减少到最高位,并清除其余部分。
我们能把它们降到最低位吗?当然可以:

x & ~(x & (x << 1))

我们正在清除比特,因此我们可以将两者合并结合起来:

x & ~(x & (x >> 1)) & ~(x & (x << 1))

似乎工作。

相关问题