java - 截断二进制对数

Question

我对这个问题有疑问，任何帮助都会很棒!

编写一个程序，将一个整数 N 作为参数并打印出其截断的二进制对数 [log2 N]。提示:[log2 N] = l 是最大整数`，使得2^l <= N。

我的心情很沮丧:

int N = Integer.parseInt(args[0]);  
    double l = Math.log(N) / Math.log(2);
    double a = Math.pow(2, l);

但是我不知道如何在保留 2^l <= N 的同时截断 l

谢谢

<小时/>

这就是我现在拥有的:

int N = Integer.parseInt(args[0]);

    int i = 0; // loop control counter
    int v = 1; // current power of two
    while (Math.pow(2 , i) <= N) {


    i = i + 1;
    v = 2 * v; 
    }

    System.out.println(Integer.highestOneBit(N)); 

这会打印出等于 2^i 的整数，该整数小于 N。我的测试结果仍然为 false，我认为这是因为问题要求打印最大的 i 而不是 N .所以当我这样做时

Integer.highestOneBit(i)

正确的 i 没有打印出来。例如，如果我这样做:N = 38，那么最高的 i 应该是 5，但它打印出 4。

然后我尝试了这个:

            int N = Integer.parseInt(args[0]);

    int i; // loop control counter
    for (i= 0; Math.pow(2 , i) == N; i++) {

    }
            System.out.println(Integer.highestOneBit(i)); 

如果我使 N = 2，我应该打印出 1，但实际上打印出 0。

除此之外我已经尝试了很多事情，但无法明白我做错了什么。帮助将不胜感激。谢谢

Answer 1

我相信您在这里寻找的答案是基于数字在计算机中实际存储方式的基本概念，以及如何在诸如此类的问题中利用它来为您带来优势像这样。

计算机中的数字以二进制存储 - 一系列 1 和 0，其中每一列代表 2 的幂:

(上图来自 http://www.mathincomputers.com/binary.html - 有关二进制文件的更多信息，请参阅 )

2的零次方在右边。因此，例如 01001 表示十进制值 2^0 + 2^3； 9.

有趣的是，这种存储格式为我们提供了一些有关该数字的附加信息。我们可以看到，2^3 是 9 的2 的最高幂。让我们想象它是它所包含的唯一的2的幂，通过砍掉除了最高的1之外的所有其他1。这是一个截断，结果如下:

01000

您现在会注意到该值代表 8 或 2^3。回到基础知识，现在让我们看看以 2 为底的对数真正代表什么。计算 2 的幂即可得到您找到的对数。 log2(8) 是 3。你能看到这里出现的模式吗？

• 最高位的位置可用作其以 2 为底的对数值的近似值。

2^3 是我们示例中的第 3 位，因此对数基数 2(9) 的截断近似值为 3。

所以 9 的截断二进制对数是 3。2^3 小于 9；这就是小于号的由来，查找其值的算法只涉及查找组成该数字的最高位的位置。

更多示例:

12 = 1100。最高位的位置 = 3(从右侧的零开始)。因此 12 = 3. 2^3 的截断二进制对数是 <= 12。

38 = 100110。最高位的位置 = 5。因此 38 的截断二进制对数 = 5。2^5 为 <= 38。

这种级别的插入位在 Java 中称为按位运算。

Integer.highestOneBit(n) 本质上返回截断值。因此，如果 n 为 9 (1001)，highestOneBit(9) 返回 8 (1000)，这可能有用。

查找数字最高位位置的一种简单方法是进行位移，直到该值为零。有点像这样:

// Input number - 1001:
int n=9;
int position=0;
// Cache the input number - the loop destroys it.
int originalN=n;

while( n!=0 ){
    position++; // Also position = position + 1;
    n = n>>1; // Shift the bits over one spot (Overwriting n).
    // 1001 becomes 0100, then 0010, then 0001, then 0000 on each iteration. 
    // Hopefully you can then see that n is zero when we've 
    // pushed all the bits off.
}

// Position is now the point at which n became zero.
// In your case, this is also the value of your truncated binary log.
System.out.println("Binary log of "+originalN+" is "+position);