算法：求N！的二进制表示中最低位1的位置，这里的位置是指什么位置

发布网友 发布时间：2022-04-14 23:27

我来回答

共2个回答

懂视网 时间：2022-04-15 03:48

题目： 对于一个字节的无符号整数变量，求其中的二进制表示中1的个数，要求算法执行效率尽可能高效。 题目解析： 这道题同样在【剑指offer】面试题10：二进制中1的个数中出现，不过在剑指offer中没有提到无符号数，因此比该题目中多考虑一个层次。下面总结这

题目：

对于一个字节的无符号整数变量，求其中的二进制表示中1的个数，要求算法执行效率尽可能高效。

题目解析：

这道题同样在【剑指offer】面试题10：二进制中1的个数 中出现，不过在剑指offer中没有提到无符号数，因此比该题目中多考虑一个层次。下面总结这道题的几种解法。

解法一（用于该题目）：

我们通常会想到除以2就是将二进制右移一位，但要判断移除的是0还是1，就要对2取余。思路很简单，通过四则运算来解答：

int Count(Byte v)
{
 int num = 0;
 while(v){
 if(v%2)
  num++;
 v /= 2;
 }
 return num;
}

对于除以2来表示二进制右移，除法的效率比直接移位的效率低得多。碰到这样的题目，尽量用移位来代替。位运算就五种形式：与、或、异或、左移和右移。在这些范围里面找到自己想要的运算。移位时要判断移除的是0还是1，那么这里就应该通过与操作判断最后一位是否为1。

int Count2(Byte v)
{
 int num = 0;
 while(v){
 if(v & 1)
  num++;
 //也可以用 num += v&1; 来代替上面两行
 v = v >> 1;
 }
 return num;
}

如果这个题目是有符号的话，当右移的时候，会在高位补充符号位，用上面两种方法的话，会陷入死循环。如何避免？可以先判断最高位，然后遍历n-1次判断除了最高位以外的位是否为1。这样的方法比较麻烦。我们可以变通一个思路，让与的那一位1不断的左移，直到将1移到最高位。

int Count3(Byte v)
{
 int num = 0;
 int flag = 1;
 while(flag){
 if(v & flag)
  ++num;
 flag = flag << 1;
 }
 return num;
}

这种方法，充分利用了二进制的相关操作，平时应该多收集这样的运算。

一个数不为0，那么二进制中肯定含1。当让这个数减去1时，最低位的1由1->0，更低位的0由0->1。当让n与n-1相与以后，n中最低位的1变成0。一次这样的操作，消去一个1，那么二进制中有多少个1，就循环多少次即可。

int Count4(Byte v)
{
 int num = 0;
 while(v){
 ++num;
 v = v & (v-1);
 }
 return num;
}

解法五（空间换时间方法）：

其实方法四已经够好了，但是因为只涉及到八位，我们可以利用选择直接选取相应的数据。比如0x1-0x2-0x4...这些都包含1个1；0x3-0x6...包含两个1；等等。通过switch语句选择相应的结果。但是这种方法效率可能比较低，因为，当输入v为255的时候，得比较到最后才能找到相应的数据。

int Count5(Byte v)
{
 int num = 0;
 switch(v){
 case 0x0:
 num = 0;
 break;
 case 0x1:
 case 0x2:
 ....
 }

 return num;
}

既然想到了利用空间换时间，我们干脆用个数组来表示，index为要查找的数，counttable[index]为该数据包含1的个数。

热心网友 时间：2022-04-15 00:56