計算所需的位數以表示2的補碼整數

Question

我必須編寫一個函數來計算以2的補碼形式表示int所需的位數。要求：

1. can only use: ! ~ &^| + << >> 
2. no loops and conditional statement 
3. at most, 90 operators are used 

目前，我想是這樣的：

int howManyBits(int x) { 
    int mostdigit1 = !!(0x80000000 & x); 
    int mostdigit2 = mostdigit1 | !!(0x40000000 & x); 
    int mostdigit3 = mostdigit2 | !!(0x20000000 & x); 
    //and so one until it reach the least significant digit 
    return mostdigit1+mostdigit2+...+mostdigit32+1; 
} 

然而，這種算法是行不通的。它也超過了90個運營商的限制。任何建議，我該如何修復和改進這個算法？

Answer 1

對於2的補碼整數，問題是負數。負數表示最重要的位：如果設置了，則表示負數。 2的補碼整數n的負值定義爲 - （1的n的補數）+1。
因此，我會首先測試負號。如果它被設置，則所需的比特數僅僅是可用來表示整數的比特數，例如， 32位。如果不是，則可以簡單地通過將n重複右移一位來計算所需的位數，直到結果爲零。如果n例如將是+1，例如， 000 ... 001，您必須將其右移一次以使結果爲零，例如， 1次。因此你需要1位來表示它。