代码之家 › 专栏 › 技术社区 › Rbutler93

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

twos-complement mask bit-manipulation c

3

Rbutler93 · 技术社区 · 11 年前

我正在研究一个函数,当x可以表示为n位时,返回1,如果不能表示为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;

}

2 回复 | 直到 6 年前

1

2

phuclv 5 年前

在您的功能中, 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

Mohit Jain 11 年前

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;
}