0

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

编写一个程序，将一个整数 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));

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

整数.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。

除此之外，我已经尝试了很多东西，但无法理解我做错了什么。帮助将不胜感激。谢谢

4

1 回答 1

1

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

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

在此处输入图像描述

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

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

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

01000

您现在会注意到该值表示 8 或 2^3。把它归结为基础，现在让我们看看 log base 2真正代表什么。这是您将 2 提高到 2 次方的数字，以获得您查找日志的内容。log2(8) 是 3。你能看到这里出现的模式吗？

  • 最高位的位置可以用作它的 log base 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);
于 2013-10-13T13:00:22.477 回答