Java: 整数中最高位1的偏移量

7 浏览
0 Comments

Java: 整数中最高位1的偏移量

为了简单起见，我们不考虑0或负数值。\n已知解决方案#1\n

return (int)(Math.log(x)/Math.log(2)); // 伪代码

\n问题：数值不稳定。对于输入x=4，可能回答2或1。\n已知解决方案#2\n

for(int i=0; ;++i)
{
    x = x >> 1;
    if(x==0)
        return i;
}

\n问题：平均复杂度为O(n)，其中n是类型中的位数。我希望能够在常数时间内得到答案。

0

2 答案

0 Comments

问题的出现原因是需要找到一个整数中最高位的1所在的位置。解决方法是使用一个预先定义好的数组，其中存储了每个可能的整数值对应的最高位1的位置。

在给出的解决方法中，首先定义了一个名为MultiplyDeBruijnBitPosition的数组，其中存储了每个可能的整数值对应的最高位1的位置。然后，通过对给定的整数进行一系列的位操作，将整数的所有位都设置为最高位1所在的位置。最后，根据设置好的位，返回整数中最高位1所在的位置。

具体的解决方法是，首先给定的整数与其自身右移1位再与上自身的按位或操作，将整数的最高1的右边的所有位都变为1。然后再将得到的结果再次与其自身右移2位再与上自身的按位或操作，将整数的最高1的右边的所有位都变为1。依次类推，将整数的最高1的右边的所有位都变为1。最后，通过与预先定义的数组中的值进行按位与操作，得到整数中最高位1所在的位置。

以上就是解决问题的方法。

0
0 Comments

在这个问题中，需要找到一个整数中最高的1位的偏移量。原文提到了一种解决这个问题的方法，即使用O(log n)（或更好）的时间复杂度。并给出了一个可以找到这个方法的网址。

在给出的网址中，我们可以找到很多关于位运算的技巧和算法。其中有一个特别适用于这个问题的算法，即"Integer Log Base 2"。这个算法的基本思想是通过不断地将整数除以2来找到最高的1位的偏移量。

具体的实现可以参考网址中的代码。通过不断地将整数除以2，直到整数变为0，可以得到最高的1位的偏移量。这个算法的时间复杂度是O(log n)，其中n是整数的位数。

所以，通过这个算法，我们可以找到一个整数中最高的1位的偏移量。这个算法的时间复杂度较低，比较高效。

0