检查是否可以使用 2 的补码中的 n 位来表示一个数

Question

我正在开发一个函数，returns 1 当 x 可以表示为 n 位时，2 的补数，如果不能，则为 0。现在我的代码适用于某些示例，例如 (5, 3)、(-4, 3)。但是我无法让它在 n 大于 x 的情况下工作，比如 (2, 6)。关于原因有什么建议吗？

我确实有一些限制，包括显式或隐式转换、相对比较运算符（<、>、<= 和 >=）、除法、模数和乘法、减法、条件（if 或 ? :)、循环、switch 语句、函数调用和宏调用。假设 1 < n < 32.

int problem2(int x, int n){

    int temp = x;
    uint32_t mask;
    int maskco;

    mask = 0xFFFFFFFF << n;
    maskco = (mask | temp);

    return (maskco) == x;

}

Answer 1

int problem2_mj(int x, int n){
    unsigned int r;
    int const mask = (-x) >> sizeof(int) * CHAR_BIT - 1;

    r = (-x + mask - (1 & mask)) ^ mask;  // Converts +n -> n, -n -> (n-1)
    return !(((1 << (n-1)) - r) >> sizeof(int) * CHAR_BIT - 1);
}

求绝对值，如果是负数则减去1
检查数字是否小于等于2^n-1

Check a working demo here

根据您更新后的要求，这里是如何添加两个数字的代码：

int AddNums(int x, int y)
{
  int carry;

  // Iteration 1
  carry = x & y;  
  x = x ^ y; 
  y = carry << 1;

  // Iteration 2
  carry = x & y;  
  x = x ^ y; 
  y = carry << 1;

  ...

  // Iteration 31 (I am assuming the size of int is 32 bits)
  carry = x & y;  
  x = x ^ y; 
  y = carry << 1;

  return x;
}

Answer 2

在你的函数中，temp 只是多余的，而 maskco 总是设置最高位，所以如果 x 是正数，它将不起作用未设置最高位的地方

简单的解决办法是屏蔽掉绝对值的最高有效位，只留下低 n 位并检查它是否仍然等于原始值。可以使用this method

计算绝对值

int fit_in_n_bits(int x, int n)
{
    int maskabs = x >> (sizeof(int) * CHAR_BIT - 1);
    int xabs    = (x + maskabs) ^ maskabs;  // xabs = |x|
    int nm      = ~n + 1U;                  // nm = -n
    int mask    = 0xFFFFFFFFU >> (32 + nm);
    return (xabs & mask) == xabs;
}

另一种方式：

int fit_in_n_bits2(int x, int n)
{
    int nm       = ~n + 1U;
    int shift    = 32U + nm;
    int masksign = x >> (shift + 1);
    int maskzero = 0xFFFFFFFFU >> shift;
    return ((x & maskzero) | masksign) == x;
}

你也可以看看oon的方式here

int check_bits_fit_in_2s_complement(signed int x, unsigned int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask))>> (n + ~0));
}

One more way

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
    int r, c;
    c = 33 + ~n;
    r = !(((x << c)>>c)^x);
    return r;
}

检查是否可以使用 2 的补码中的 n 位来表示一个数

Check if a number can be represented using n bits in 2’s complement

c

bit-manipulation

mask

twos-complement