计算 Ruby 中整数的二进制描述中的前导数

Question

我正在搜索一个快速函数（没有字符串）

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

感谢您的努力！

Answer 1

这可能不是最有效的解决方案，但它确实有效。

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

Answer 2

到目前为止，这是我的方法：

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

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

添加：

好的，已经很快了，我想我会采用这个解决方案。但是另一个没有循环的就完美了:-)

欢迎提出想法！

添加：

不要用我的方法。它会产生舍入误差。查看所选答案以获得正确版本。

Answer 3

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 and Fixnum#[]。

Answer 4

带循环的版本实际上要快一点，但是 FWIW，这是没有循环的版本：

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

计算 Ruby 中整数的二进制描述中的前导数

Calculate leading ones in binary depiction of integer in Ruby

ruby

binary

bits