Hi guys would you mind explaining to me this code? Especially the code where the

Question

Hi guys would you mind explaining to me this code? Especially the code where the mask part. In my ubderstanding, the mask is supposed to represent 1,2,4,8, and 16. But then why is that it's 0x2 for 1 bit? Or am i missing the point. Please explain in detail or perhaps with example.

/* howManyBits - return the minimum number of bits required to represent x in

* two's complement

* Examples: howManyBits(12) = 5

* howManyBits(298) = 10

* howManyBits(-5) = 4

* howManyBits(0) = 1

* howManyBits(-1) = 1

* howManyBits(0x80000000) = 32

* Legal ops: ! ~ & ^ | + << >>

* Max ops: 90

* Rating: 4

*/

int howManyBits(int x) {

  int y, result, mask16, mask8, mask4, mask2, mask1, bitnum;

 /*

* The idea here is to apply binary search in order to get log number of operations

*/

  mask1 = 0x2; // 0x1 << 1

  mask2 = 0xC; // 0x3 << 2

  mask4 = 0xF0; // 0x000000F0

  mask8 = 0xFF<<8; // 0x0000FF00

  mask16 = (mask8 | 0xFF) << 16;// 0xFFFF0000

  result = 1;

  y = x^(x>>31); //cast the number to positive with the same howManyBits result

  // Check first 16 bits, if they have at least one bit - result > 16

  bitnum = (!!(y & mask16)) << 4; // 16 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask8)) << 3; // 8 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask4)) << 2; // 4 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask2)) << 1; // 2 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = !!(y & mask1); // 1 OR zero

  result += bitnum;

  y = y >> bitnum;

  return result + (y&1);

}

Explanation / Answer

/* howManyBits - return the minimum number of bits required to represent x in

* two's complement

* Examples: howManyBits(12) = 5

* howManyBits(298) = 10

* howManyBits(-5) = 4

* howManyBits(0) = 1

* howManyBits(-1) = 1

* howManyBits(0x80000000) = 32

* Legal ops: ! ~ & ^ | + << >>

* Max ops: 90

* Rating: 4

*/

int howManyBits(int x) {

  int y, result, mask16, mask8, mask4, mask2, mask1, bitnum;

/*

* The idea here is to apply binary search in order to get log number of operations

*/

  mask1 = 0x2; // 0x1 << 1

  mask2 = 0xC; // 0x3 << 2

  mask4 = 0xF0; // 0x000000F0

  mask8 = 0xFF<<8; // 0x0000FF00

  mask16 = (mask8 | 0xFF) << 16;// 0xFFFF0000

  result = 1;

  y = x^(x>>31); //cast the number to positive with the same howManyBits result

  // Check first 16 bits, if they have at least one bit - result > 16

  bitnum = (!!(y & mask16)) << 4; // 16 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask8)) << 3; // 8 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask4)) << 2; // 4 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = (!!(y & mask2)) << 1; // 2 OR zero

  result += bitnum;

  y = y >> bitnum;

  bitnum = !!(y & mask1); // 1 OR zero

  result += bitnum;

  y = y >> bitnum;

  return result + (y&1);

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.