注：文章为方便说明，规定位宽为16
想要在一个16位的补码中无视多余位，找出可以表示该带符号整数二进制补码的最少位数，我们需要借鉴到C语言中一个非常有用的算法思想——拆半查找。
由于带符号整数需要讨论数的正负，所以我们进行一个操作，来使得我们的算法更加容易执行——取反，我们先判断x是正数还是负数，如果是负数我们就对其进行取反操作，正数则不进行任何操作。 为什么进行取反呢，我们需要知道取反并不会影响有效位数，例如1111111010010101有效位数为10，当我们进行取反后变为0000000101101010有效位数为10，为什么是有效位数是10而不是9呢？因为我们需要一位符号位来区分一个数是正数还是负数。 取反之后，进行拆半操作，如果前16位有值（既不为0），则我们看前16位，且我们至少需要16位，那么我们就无须再看后16位了，我们通过算术右移操作（因为取反操作，所以算术右移等价于逻辑右移），将后16位移走。之后的操作与上面类似知道拆到不能再拆为止。如果前16位全为0， 则我们看后16位，我们不进行移位操作，再对后16位进行拆半操作。
举例来说： 42的补码表示为0000000000101010 由于第一次拆半结果为（00000000，00101010），高8位都为0，则看低8位； 再对低8位进行拆半，结果为（00000000，0010，1010），高4位有值，则我们至少需要4位，右移4位； 再对高4位进行拆分，结果为（000000000000，00，10），高2位为都0，则看低2位； 再对低2位进行拆半，结果为（00000000000000，1，0），高1位有值，则我们至少需要1位； 于是我们得42的二进制补码表示的最少位数=4+1+2=7
再如 -42的补码表示为1111111111010110 先取反得0000000000101001 第一次拆半结果为（00000000，00101001），高8位位0，则我们看低8位； 再对低8位进行拆分，结果为（000000000，0010，1001），高4位有值，则我们至少需要4位，右移4位； 再对高4位进行拆分，结果为（000000000000，00，10），高2位为0，则我们看低2位； 再对低2位进行拆分，结果为（00000000000000，1，0），高1位有值，则我们至少还需要1位； 于是我们得到-42的二进制补码表示的最少位数=4+1+2=7
看到这里，可能会有人不明白，为何我们最后都要加上2，当我们拆到还剩两位的时候，只会有三种情况01，10，11，根据上面所说的01的话则我们看低1位，但是1位已经不能再拆了，但是我们结果是要将每一层的至少需要的位数相加，我们就将这个1忽略了，所以需要人为的加上一位以及符号位；而10的话，我们看高1位，高1位也不能再拆，同理这个1也被忽略掉了，我们也需要人为的加上一位和符号位。
综上，我们在至少需要的位数相加的基础上还要人为的加上2。
代码如下（位宽为32）：
#include <iostream> #include <stdio.h> #include <stdlib.h> #define OK 1 using namespace std; int HalfSearch(int &temp,int &Sum,int &shift){ //递归拆半思想 int bit; bit=(temp>>shift) ? shift : 0;//how many bits that we still need temp=temp>>bit; shift=shift/2; Sum=Sum+bit; if(!shift) return OK; HalfSearch(temp,Sum,shift); } int howManyBits(int x){ //先判断x是正数还是负数 //如果是负数则对x取反 //再利用拆半查找法的思想进行查找 int temp,Sum=2,shift=16; int sign=x>>31; if(sign) temp = ~x; else temp = x; HalfSearch(temp,Sum,shift); return Sum; } int main() { int x,ret; cin>>x; ret=howManyBits(x); cout<<"Bits="<<ret<<endl; return 0; }运行实例：
