如果该位介于低和高之间，则将 0 位变为 1 位

Question

完全公开，这是一个家庭作业问题，我不需要确切的代码。我的任务是仅使用 ~ & + <<.

重现以下代码

int result = 0;
int i;
for(i = lowbit; i <= highbit; i++)
    result |= 1 << i;
return result;

其中lowbit和highbit是介于0和31之间的参数。如果 lowbit 比 highbit 大，return 0.

我试过的是下面的代码

int result = 0;
int negone = ~0x0;
int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location
int last = 1 << (highbit + negone); //the last 1 bit is at the highbit th location
int tick = ~(first + last); //attempting to get all bits in the range of low and highbit.
result = ~(~first & ~tick); //bitwise | without using |
result = ~(~last & ~result);
return result + 1; //the first bit should always be on.

那么我在这里缺少一些基本的东西吗？除了我没有做的事情之外，这也超出了我允许使用的 12 个操作员的限制，但我想在我开始限制操作员之前尝试让它工作。

当我运行测试脚本时，我在大多数测试中遇到错误，包括 lowbit 和 highbit 彼此相等。 highbit 是最大尺寸而 lowbit 是最小尺寸的情况似乎可行。

如有任何帮助，我们将不胜感激。

Answer 1

原代码生成一个1的块，从lowbit一直到highbit（含）。这可以在没有循环的情况下实现，如下所示：

int nrOfBits = highbit + ~lowbit + 2;  // highbit - lowbit + 1
int shift = (nrOfBits & 0x1f + 1);
int result = ~(~(1 << shift)+1) << lowbit;

这个想法是，例如用1填充的8位范围表示255的数量，而2^8是256。所以 - 由于不允许运算符 -，我们使用 2 补码得到 -256，添加 1 得到 -255，然后将其转回 +255使用 2 补码运算符 ~。然后，我们只需要将方块 lowbits 向左移动即可。

Answer 2

1) 创建一个从低位到高位设置的掩码：

uint32_t mask = ~(~0ul << highbit << 1) & (~0ul << lowbit)

示例：低位 = 4，高位 = 12（9 位）

mask = ~(0xffffffff << 12 << 1) & (0xffffffff << 4)
     = ~(0xffff7000) & 0xfffffff0
     =   0x00001fff  & 0xfffffff0
     =   0x00001ff0

2) 将掩码应用于要修改的值，这最简单的是 | 操作，但在本练习中这不是有效的运算符，因此必须使用 De Morgan 的论坛进行转换：

A|B -> ~(~A & ~B) :

result = ~(~result & ~mask) ;

当然可以将这两个步骤结合起来，但这样可能就不够清晰了。

Answer 3

negone 应该这样初始化：

uint32_t negone = ~0UL;

您正在添加具有位模式的位号：

int first = 1 << (lowbit + negone); //the first 1 bit is at the lowbit th location
int last = 1 << (highbit + negone);

您应该改为计算 32 位掩码

uint32_t first = negone << lowbit;  // all bits below lowbit are 0, others are 1
uint32_t last = negone << highbit << 1;  // all bits above highbit are 1, other are 0

用last掩码first的补码得到结果：

uint32_t result = ~first & last;

结合上述步骤给出了一个直接的解决方案，有 7 个运算符（12 个包括括号和赋值），没有加法，也没有减法：

uint32_t result = ~(~0UL << highbit << 1) & (~0UL << lowbit);

我使用 0UL 因为类型 unsigned long 保证至少有 32 位，而类型 unsigned int 可能只有 16 位。

Answer 4

问题可能是 tick = ~(first+last) 没有将位从低位翻转到高位。

也许我们可以这样做：

/* supposed that lowbit = 1, highbit = 2 */
uint32_t negone = ~(0u); /* negone = all 1s */
uint32_t first = negone << lowbit;  /* first = ...111110 */
uint32_t last = (1 << (highbit + 1)) + negone; /* last = ...0000111 */
uint32_t tick = last & first; /* tick = ...000110 */
result = ~(~result&~tick); /* Bitwise Or without | as you mentioned. */

需要11位运算才能完成。

p.s。我想知道为什么第一位应该始终打开。

编辑：为了避免未定义的操作，我们应该使用无符号类型，如uint32_t。

如果该位介于低和高之间，则将 0 位变为 1 位

Turn 0 bits to 1 bits if the bit is between low and high

c

bit-shift

bitwise-operators