循环遍历整数中的位，ruby

我正在编写一个程序，其中一个问题是我需要对某些整数中的位模式进行一些分析。

因此，我希望能够做到这样的事情：

#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方法的性能更差

这个循环将被执行数百万次或更多次，所以我希望它尽可能快。

作为参考，这是整个function

 @@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 

Answer 1

要确定连续1的最长序列的长度，这更有​​效：

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

该方法简单地计算您可以“按位AND”数字的次数，其自身向右移位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 

Answer 2

Ruby可能不是您项目的好选择。 ruby的力量不是它的表现，而是它可以让你做的事情如下：

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

而不是写大量的代码。 如果你不介意编写复杂的代码（你似乎并不这样做），那么任何其他语言都可能表现得更好。

Answer 3

请注意，o和“0”在ruby中的布尔值都为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 

Answer 4

在Ruby中， Integer （即Bignum和Fixnum都可以）就像它们是位数组一样被索引。 但是，它们不是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 

（或者0b10111110.to_a.chunk …如果您更喜欢较少侵入性的方法。）

如果您担心性能，您选择的执行引擎会产生很大的不同。 例如，Rubinius或JRuby的优化编译器可能能够内联和优化YARV相当简单的编译器无法进行的许多方法调用。 YARV对Fixnum的特殊治疗可能使其优于MRI。

从示例中可以看出，我是无点样式和函数式编程的忠实粉丝。 如果您可以通过分析certificate您在代码中的特定点处存在瓶颈，则可能需要将其替换为稍微不那么优雅或不纯的版本，或者您可能需要手动融合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 

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< 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表达forms，而不是在表初始化中做按位逻辑，因为它不再是瓶颈点 - - 虽然我会坚持使用逐位数学只是为了清晰的表达而不是字符串解析。 每个查找只需要2个表查找，一个添加和一个max

Answer 6

有时使用字符串是最明显的方法，性能是可以容忍的：

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

Answer 7

算法

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

该算法的步骤如下，但读者很多人通过首先阅读以下部分（“插图”）更容易理解。

1. 设置longest为0 。
2. 设置len等于n的位数（ len = n.bit_length ）。
3. 如果len <= 2 ，则返回答案（ 0或2 ）。
4. 确定n的中间位中间的索引（ 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 （ cand ）中最长的1位字符串。 设置longest = [longest, cand].max 。
10. 如果ri < 0转到步骤11; 否则设置rn等于由索引0 （最低有效）到ri （最高有效）的位组成的数字。 递归地设置为n到rn并转到步骤2.这将返回该数字rn ( cand ). Set最长的1位字符串). Set ). Set最长= [最长，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 （第二个数字中的前导零点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 

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) #=> #:each> enum.to_a #=> [[0], [0], [1, 1, 1], [0], [1, 1, 1, 1], [0], # [1, 1, 1], [0], [0], [0], [1, 1]]