java - 将 1 到 N 中所有设置位数为 2 的数字相加

Question

我有一个问题，我必须将 1 到 N 的数字相加，它们的设置位为 2。就像 N = 5 一样，我们应该得到值 8，因为数字 3 和 5 的 2 位设置为 1。我在 java 中实现相同的。我正在为 int 值获取正确的 o/p 但是当涉及到 long 值时，它要么花费大量时间要么卡住，当我在代码判断站点上提交相同的值时，它会给出运行时间超出的消息。请指导我如何优化我的代码以更快地运行它，谢谢 :)

public static void main(String[] args)
{
    long n = 1000000L;
    long sum = 0;
    long start = System.currentTimeMillis();
    for(long i = 1L ; i <= n ; i++)
    {
        if(Long.bitCount(i) == 2)
        {
            sum += i;
        }
    }
    long end = System.currentTimeMillis();
    System.out.println(sum);
    System.out.println("time="+(end-start));
}

Answer 1

正如@hbejgel 指出的那样，遍历所有数字并检查它们的位数是没有意义的。您可以简单地用 2 位构造数字并将它们相加。

您可以通过在 long 中选择两个不同的位位置，即“高位”位和“低位”位来构造一个 2 位的数字:

long i = (1 << higher) + (1 << lower);

因此，您可以简单地遍历所有这些数字，直到您构建的值超过您的限制:

long sum = 0;
outer: for (int higher = 1; higher < 63; ++higher) {
  for (int lower = 0; lower < higher; ++lower) {
    long i = (1 << higher) + (1 << lower);
    if (i <= n) {
      sum += i;
    }
    if (i >= n) break outer;
  }
}