在 Ruby 中计算整数的二进制表示中前导 1 的个数

Question

我正在寻找一种快速的函数（不涉及字符串）

leading_ones(0b11101)      # =>3
leading_ones(0b1111000110) # =>4

感谢您的努力！

- user3756502

---

你为什么需要这个，你尝试过什么？ - max pleaner

它属于解决更大问题的一种方法，请参见此处：http://stackoverflow.com/questions/39318312/binary-calculations-ruby - user3756502

似乎是一个作业问题（为什么不使用字符串？），但我很想看到答案，无论出于好奇心。 - max pleaner

这不是作业。应该让图形用户界面更高效。字符串太慢了。 - user3756502

你要转换的整数是否有最大（二进制）长度限制？ - Stefan

不是真的。无法预测明确的最大长度。 - user3756502

Answer 1

def leading_ones(n)
  nbr = 0
  (n.bit_length-1).downto(0) do |i|
    return nbr if n[i].zero?
    nbr += 1
  end
  nbr
end

leading_ones(6)
  #=> 2

注意：6.to_s(2) #=> "110"。这里使用了方法Fixnum#bit_length和Fixnum#[]。

- Cary Swoveland

---

非常感谢！我之前不知道函数bit_length的存在，最近才发现我一直在使用的替代方案Math.log2存在四舍五入误差。你提供了正确实现我的方法的帮助。非常感谢！！！ - user3756502

Answer 2

这可能不是最高效的解决方案，但它能够正常工作。

def leading_ones(num)
  counter = 0
  while num > 0
    if num % 2 == 0
      counter = 0
    else
      counter += 1
    end

    num = num / 2
  end
  counter
end

leading_ones(0b111) # => 3
leading_ones(0b11101) # => 3
leading_ones(0b111101) # => 4
leading_ones(0b1000) # => 1
leading_ones(0b01000) # => 1

- jan.zikan

---

谢谢 kallax。我记得你在我的第一个有关此问题的问题中：http://stackoverflow.com/questions/39297163/trying-to-store-many-rectangles-without-duplicate-areas-efficiently-in-ruby有没有不需要循环的想法？那太好了！ - user3756502

Answer 3

您使用循环的版本实际上略微更快，但是无论如何，这里是一个不使用循环的版本：

def leading_ones(n)
    # Number of bits needed to hold `n` as an unsigned integer
    bits = n.bit_length
    # `digits` bits, all on
    max_possible = (1 << bits) - 1
    # Flips all of `n`'s bits
    flipped = n ^ max_possible
    # First right-index of a zero in `n`, or the first index of a 1 in `flipped`
    first_zero_rindex = flipped.bit_length
    # Left-index of the first zero
    first_zero_index = bits - first_zero_rindex
    first_zero_index
end

- nloveladyallen

---

在底层，bit_length 基本上是一个循环。顺便说一下，你可以使用 (1 << bits) - 1 来避免昂贵的指数运算。 - Stefan

在底层，肯定有许多循环。但是如果我在高层级别上添加额外的循环，通常会变得更慢。感谢你们的贡献！ - user3756502

@Stefan 我很惊讶Ruby没有将2 ** n优化为1 << n，其中n是正整数。不过，我编辑了我的答案，使用位移来计算max_possible。 - nloveladyallen

Answer 4

这是我目前的方法：

def leading_ones(arg)
    c=0
    log=Math.log2(arg).to_i
    max_index.downto(0){|i|
        if arg[i]==1
            c+=1
        else
            return c
        end
    }
    return c
end

有没有不用循环的想法？我认为可以在不迭代的情况下从另一个数字计算出一个数字。

添加：

好的，它已经非常快了，我想我会采用这个解决方案。但是另一个不需要循环的解决方案将是完美的 :-)

欢迎提出想法！

添加：

不要使用我的方法。它会产生舍入误差。请参阅所选答案以获取正确版本。

- user3756502