在整数中循环位，Ruby。

Question

我正在编写一个程序，其中一个问题是需要分析一些整数中的比特模式。

因此，我希望能够像这样做：

#Does **NOT** work:
num.each_bit do |i|
   #do something with i
end

我通过以下方式成功实现了：

num.to_s(2).each_char do |c|
   #do something with c as a char
end

然而，这并不具备我想要的性能。

我发现你可以这样做：

0.upto(num/2) do |i|
   #do something with n[i]
end

这个方法的性能比each_char方法还要差。

这个循环可能会被执行数百万次，甚至更多，因此我希望它尽可能快。

供参考，以下是整个函数的内容：

@@aHashMap = Hash.new(-1)

#The method finds the length of the longes continuous chain of ones, minus one 
#(101110 = 2, 11 = 1, 101010101 = 0, 10111110 = 4)

def afunc(n) 
if @@aHashMap[n] != -1
    return @@aHashMap[n]
end

num = 0
tempnum = 0
prev = false

(n.to_s(2)).each_char do |i|
    if i
        if prev
            tempnum += 1
            if tempnum > num
                num = tempnum
            end
        else
            prev = true
        end
    else
        prev = false
        tempnum = 0
    end
end

@@aHashMap[n] = num
return num
end

- Automatico

---

如果你追求性能，建立一个查找表可能是这种情况下正确的优化方式。 - J. Holmes

声明一个 @@ 类型的变量非常不寻常。你有充分的理由这样做吗？ - tadman

在大多数情况下，您应该在类的实例内部使用标准的@变量来保持组织。 @@是类变量。 - tadman

我觉得我可能漏掉了什么，但是为什么不能像这样遍历位：当n > 0时 val = (n & 1); n = n >> 1; 输出val; 结束 - Donato

你的问题似乎很受欢迎，这可以从点赞数量和大量答案中看出，其中一些答案非常创新。问题在于你的问题不够清晰，只有通过阅读代码才能理解。因此，一些读者可能会跳过这个问题，在未来，你的问题可能不太可能出现在相关搜索结果中。我建议你编辑以澄清问题... - Cary Swoveland

Answer 1

为确定连续1的最长序列长度，以下方法更有效：

def longest_one_chain(n)
  c = 0
  while n != 0
    n &= n >> 1
    c += 1
  end
  c
end

这个方法简单地统计了将数字与自己向右移动1位进行“按位与”操作的次数，直到为零。

例如：

                 ______ <-- longest chain
    01011011100001111110011110101010 c=0
AND  0101101110000111111001111010101
        1001100000111110001110000000 c=1, 1’s deleted
AND      100110000011111000111000000
            100000011110000110000000 c=2, 11’s deleted
AND          10000001111000011000000
                    1110000010000000 c=3, 111’s deleted
AND                  111000001000000
                     110000000000000 c=4, 1111’s deleted
AND                   11000000000000
                      10000000000000 c=5, 11111’s deleted
AND                    1000000000000
                                   0 c=6, 111111’s deleted

- Stefan

---

太棒了！:D 我还找到了另一种方法，基本上是通过递归位移和计数来实现的。不过这个更好！ - Automatico

最长的1链 -17 - Cary Swoveland

@CarySwoveland 有趣的问题！但是负数的最长1链是什么呢？我认为您必须考虑位长度才能得到有意义的结果。因此，对于8位，您可以传递239而不是-17，即[-17].pack('c').unpack1('C')。 - Stefan

我也看到了 -17 & 255 #=> 239。 - Cary Swoveland

Answer 2

对于你的项目来说，Ruby可能不是一个好的选择。Ruby的优点并不在于性能，而是它允许您做一些像这样的事情:

n.to_s(2).scan(/1+/).sort.last.length - 1

除了写大量代码外，如果您不介意编写复杂的代码（您似乎并不介意），任何其他编程语言都可能表现更好。

- pguardiario

---

n.to_s(2).scan(/1+/).max_by(&:length).length - 1 应该会更快一些。 - Cary Swoveland

Answer 3

请注意，在Ruby中，o和“0”都具有布尔值为true的值，因此“if i”将不会给出您想要的结果。

当然，应该避免将每个数字转换为字符串。 Fixnum有一个方法[]来访问数字的位，因此这有可能更快。

如果您已经尝试过这个：

0.upto(num/2) do |i|
   #do something with n[i]
end

如果使用num/2，可能会导致循环次数过多。

对于32位整数，应该使用：

0.upto(31) do |i|
   if n[i] == 1
     ...
   end
end

- Meier

---

文档参考 - J. Holmes

0.size*8 表示位数的数量。 - steenslag

Answer 4

在Ruby中，整数（即包括大整数和小整数在内的Integer）已经可以像位数组一样进行索引。但是，它们并不属于Enumerable。

当然，你可以修复这个问题：

class Integer
  include Enumerable

  def each
    return to_enum unless block_given?      
    (size*8).times {|i| yield self[i] }
  end
end

一种稍微不那么侵入式的方法可能是将Integer表示为数组：

class Integer
  def to_a
    Array.new(size*8, &method(:[]))
  end
end

然后你可以使用Ruby的巧妙的Enumerable方法：

0b10111110.chunk {|b| true if b == 1 }.map(&:last).max_by(&:size).size - 1

< p >（或者如果您更喜欢不那么显眼的方法，可以使用0b10111110.to_a.chunk …）

如果您担心性能问题，选择的执行引擎会有很大影响。例如，Rubinius或JRuby的优化编译器可以内联和优化许多YARV的简单编译器无法处理的方法调用。 YARV对于Fixnum的特殊处理可能使其比MRI具有优势。

从示例中可以看出，我非常喜欢点无式风格和函数式编程。如果您可以通过分析证明代码中的某个特定点存在瓶颈，您可能需要将其替换为稍微不那么优雅或不那么纯粹的版本，或者您可能希望手动融合map和max_by。

class Integer
  def to_a
    Array.new(size*8) {|i| self[i] }
  end
end

0b10111110.chunk {|b| true if 1 == b }.map {|key, chunk| chunk.size }.max - 1

或者

0b10111110.chunk {|b| true if 1 == b }.max_by {|key, chunk| chunk.size }.last.size - 1

- Jörg W Mittag

Answer 5

如果您正在寻找性能，那么构建查找表可能是最高效的方式。特别是如果您正在一个紧密的循环中执行这些操作：

class BitCounter
    def initialize
        @lookup_table = (0..65535).map { |d| count_bits(d) }
    end

    def count(val)
        a,b,c = @lookup_table[val & 65535]
        d,e,f = @lookup_table[val >> 16]
        [a,b,c+d,e,f].max
    end

private

    def count_bits(val)
        lsb = lsb_bits(val)
        msb = msb_bits(val)
        [lsb, inner_bits(val, lsb, msb), msb]
    end

    def lsb_bits(val)
        len = 0
        while (val & 1 == 1) do
            val >>= 1
            len += 1
        end
        len
    end

    def msb_bits(val)
        len = 0
        while (val & (1<<15) == (1<<15)) do
            val <<= 1
            len += 1
        end
        len
    end

    def inner_bits(val, lsb, msb)
        lens = []
        ndx = lsb

        len = 0
        (lsb+1..(15-msb)).each do |x|
            if ((val & (1<<x)) == 0)
                if(len > 0)
                    lens << len
                    len = 0
                end
            else
                len += 1
            end
        end
        lens.max || 0
    end
end

然后是一个例子：

counter = BitCounter.new
p counter.count 0b01011011100001111110011110101010  // 6

这基本上为所有16位值创建了一个查找表，然后从这些缓存的值中计算出最大结果。

您甚至可以结合更具表现力的形式n.to_s(2).scan(/1+/).sort.last.length - 1而不是在表格初始化中执行位逻辑，因为它不再是瓶颈点--尽管我会坚持使用位数学来清晰地表达而不是字符串解析。每次查找只需要2个表查找、一个加法和一个max。

- J. Holmes

---

这看起来是一个不错但复杂的解决方案。等我回来再试试。然而，我发现我的问题需要加速1000倍或更多，潜在地需要执行数百万次，所以我认为我需要离开Ruby进行这个项目。但这个Ruby代码非常好用。 - Automatico

我有这样的印象，即OP想要确定任意大整数中最长的连续1字符串。 - Cary Swoveland

Answer 6

有时使用字符串是最明显的方法，而且性能也可以接受：

def oneseq(n)
  n.to_s(2).split(/0+/).sort_by(&:length).last.to_s.length
end

- tadman

---

性能在这个小应用程序中非常关键，因此我实际上需要转向C++和一些OpenCL或CUDA解决方案。我发现手头的问题对于Ruby来说太大了。 - Automatico

如果您需要每秒千兆字节级别的性能，那么您将需要更基于C的解决方案，但更重要的是，需要一个擅长提取1序列的算法。不要忘记，在性能关键部分内嵌C并不太难。例如：rubyinline - tadman

我知道用 Ruby 可以实现，但这个问题需要多线程处理。而且是重度的多线程处理。基本上我已经想到需要使用 GPU 处理，或者如果我非常不幸的话，需要使用超级计算机处理。那样的话，我就麻烦了。 - Automatico

这有点偏离实际问题的主题，但是：我基本上正在进行一种算法来找到一个范围的总和。唯一的问题是，这个范围产生的数字非常巨大，以至于我无法理解问题的规模。不仅数字本身很大，而且我必须对其前面的所有数字进行计算，以确定此当前数字的输出。然后我必须找到该数字的第N次出现，其中N与第一个数量级相同。所以，我有一个问题。 :p - Automatico

Automatico，我建议您发布一个描述您实际问题的问题，不要假设应该采取什么方法来解决它。您可能会惊讶于建议的创新算法。 - Cary Swoveland

Answer 7

算法

可以考虑使用二分查找。我已经实现了以下算法来确定给定非负整数n中最长的1位字符串的长度。计算复杂度为O（n），但对于许多n的值，它将接近O（log₂（n））。

算法步骤如下，但读者可能会更容易地通过先阅读以下部分（“说明”）来跟随它们。

1. 将longest设置为0。
2. 将len设置为n的位数（len = n.bit_length）。
3. 如果len <= 2，则返回答案（0、1或2）。
4. 确定中间位n的索引mid（mid = len/2或mid = len >> 1）。
5. 将ri = mid+1和li = mid-1。
6. 如果中间位的值（n[mid]）为零，则转到步骤10。
7. （n[mid] = 1才能到达此步骤。）确定最大索引li >= mid和最小索引ri <= mid，使得对于所有ri <= i <= li，都有n[i] = 1。
8. 设置longest = [longest, ri-li+1].max，li += 1和ri -= 1。
9. 如果li == len，则转到步骤10；否则，将ln设置为由索引li（最不重要的）到len-1（最重要的）的位组成的数字。递归地将n设置为ln并转到步骤2。这将返回数字ln中最长的1位字符串（cand）。设置longest = [longest, cand].max。
10. 如果ri < 0，则转到步骤11；否则，将rn设置为由索引0（最不重要的）到ri（最重要的）的位组成的数字。递归地将n设置为rn并转到步骤2。这将返回数字rn中最长的1位字符串（cand）。设置longest = [longest, cand].max`。
11. 在递归中返回longest。

说明

假设

n = 0b1010011011101011110
  #=> 341854

那么

len = n.bit_length
  #=> 19
mid = len >> 1
  #=> 9
n[mid]
  #=> 1
longest = 0

我们可以将n描述如下

101001101 1 101011110

其中中间的位 1 很显眼。由于它是一个 1，我们向左右寻找连续的 1 序列。我们得到以下结果。

10100110 111 01011110

由于我们发现了三个1，因此我们更新longest。

longest = [longest, 3].max
  #=> [0, 3].max => 3

我们现在需要检查0b10100110和0b1011110（第二个数字的前导零被舍去）。

对于左边的数字，我们做如下计算。

n = 0b10100110
len = n.bit_length
  #=> 8
mid = len >> 1
  #=> 4
n[mid]
  #=> 0

所以我们有

101 0 0110

（注意n [0]是最低有效位）。 我们可以排除 0b101 和 0b110 ，因为两者都有 3 位，这不超过当前值 longest 的 3 。

现在我们考虑右半部分，

n = 0b1011110
len = n.bit_length
  #=> 7
mid = len >> 1
  #=> 3
n[mid]
  #=>1

所以我们有

101 1 110

由于 n[mid] #=> 1，我们向左右查找连续的1字符串并获得

10 1111 0

当我们发现了一个由4个1组成的字符串时，我们设置

longest = [longest, 4].max
  #=> [3, 4].max = 4

最后我们可以看到左侧数字的位数（2）和右侧数字的位数（1）都小于3，所以我们完成了计算，并返回longest #=> 4。（实际上，OP想要longest - 1 #=> 3，我们将其视为一个辅助计算。）

代码

def longest_run(n, longest=0)
  len = n.bit_length
  return [longest, (n & 1) + (n >> 1)].max if len <= 2
  mid = len >> 1
  ri = mid-1
  li = mid+1
  if n[mid] == 1
    until n[ri] == 0
      ri -= 1
    end
    until n[li] == 0
      li += 1
    end
    cand = li-ri-1
    longest = cand if cand > longest
  end
  if ri >= 0
    shift = ri+1
    m = n ^ ((n >> shift) << shift)
    if m.bit_length > longest 
      cand = longest_run(m, longest) 
      longest = cand if cand > longest
    end
  end
  if li <= len - 1
    m = n >> li
    if m.bit_length > longest 
      cand = longest_run(m, longest) 
      longest = cand if cand > longest
    end
  end
  longest
end

示例

longest_run 341854
  #=> 4
longest_run 0b1011110011111000000111100011101111011110
  #=> 5
longest_run 0b101111001111100000011110001110111111011111
  #=> 6
longest_run 2**500_000-1
  #=> 500000
longest_run ("10"*100_000).to_i(2)
  #=> 1

- Cary Swoveland

---

对于数字 n = 0b1001100111000，我可能希望提取出最后的 6 位：111000。我使用了 Integer#^ ("exclusive or") 来实现：ri = 5; n ^ ((n >> ri+1) << ri+1) #=> 0b111000。这个方法可以工作，但我认为应该有更好的方法。我考虑过 n & (2**(ri+1)-1)，但 Ruby (MRI v2.5.1) 似乎不喜欢大的 2 的幂次方：puts 2**100000000 #=> warning: in a**b, b may be too big。另一种方法是 n & ("1"*(ri+1)).to_i(2)。读者们能否建议提取正整数最后 m 位的最佳方法？ - Cary Swoveland

num.digits(2).first(m)可能会做到这一点（以相反的顺序）。 - steenslag

@steenslag，很有趣。（我不知道digits可以作为参数接受一个基数。）当然，我仍然需要将零和一的数组转换回整数。 - Cary Swoveland

Answer 8

这里还有几种更简单的方法（虽然我认为@Steven的答案和我的其他答案会更有效率）。

#1

def max_string_of_ones(n)
  max_length = 0
  cand = 0
  (0..n.bit_length).reduce(0) do |max_length, i|
    if n[i] == 1
      cand += 1
    else
      max_length = cand if cand > max_length
      cand = 0
    end
    max_length
  end
end

注意 n[n.bit_length] #=> 0。

#2

这个第二种方法使用了 Ruby 的 翻转-流泪操作符。另外，我想过，“如果 Integer 有一个返回枚举器的 each_bit 方法，那不是很方便吗？”，于是我就添加了这个方法。

class Integer
  def each_bit
    Enumerator.new do |yielder|
      if block_given?      
        bit_length.times { |i| yielder << yield(self[i]) }
      else
        bit_length.times { |i| yielder << self[i] }
      end
    end
  end
end

def max_string_of_ones(n)
  n.each_bit.slice_before { |b| true if b==0 .. b==1 }.max_by(&:size).size
end

max_string_of_ones(0b1100011101111011100)
  #=> 4

请注意以下中间计算。

def max_string_of_ones(n)
  n.each_bit.slice_before { |b| true if b==0 .. b==1 }
end

enum = max_string_of_ones(0b1100011101111011100)
  #=> #<Enumerator: #<Enumerator::Generator:0x00000000019a2f80>:each>
enum.to_a
  #=> [[0], [0], [1, 1, 1], [0], [1, 1, 1, 1], [0],
  #    [1, 1, 1], [0], [0], [0], [1, 1]]

- Cary Swoveland