CODEWITHSUNDEEP
cbit-manipulationmasktwos-complement
Rbutler93
Rbutler93

Reputation: 73

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

I'm working on a function that returns 1 when x can be represented as an n-bit, 2’s complement number and 0 if it can't. Right now my code works for some examples like (5, 3), (-4, 3). But I can't get it to work for instances where n is bigger than x like (2, 6). Any suggestions as to why?

I do have restrictions though which include casting, either explicit or implicit, relative comparison operators (<, >, <=, and >=), division, modulus, and multiplication, subtraction, conditionals (if or ? :), loops, switch statements, function calls, and macro invocations. Assume 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;

}

Upvotes: 3

Views: 1637

Answers (2)

phuclv
phuclv

Reputation: 41794

In your function, temp is just redundant, and maskco always have the top bit(s) set, so it won't work if x is a positive number where the top bit isn't set

The simple solution is to mask out the most significant bits of the absolute value, leaving only the low n bits and check if it's still equal to the original value. The absolute value can be calculated using 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;
}

Another way:

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

You can also check out oon's way 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;
}

Related:

Upvotes: 2

Mohit Jain
Mohit Jain

Reputation: 30489

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. Find the absolute value and subtract 1 if the number was negative
  2. Check if number is less than or equal to 2n-1

Check a working demo here

As per your updated request here is the code how to add two numbers:

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

Upvotes: 2

Related Questions