Looping Through Bits in an Integer, Ruby

Looping through bits in an integer, ruby

To determine the length of the longest sequence of consecutive 1's, this is more efficient:

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

The method simply counts how many times you can "bitwise AND" the number with itself shifted 1 bit to the right until it is zero.

Example:

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

Make array of bools out of Ruby integer bits

Try this:

x = 5.to_s(2).split(//).collect do |n|
  n == "1"
end

p x

Ruby .times method called on an integer. How does it know to iterate through each integer as the argument in a block?

The times method actually returns a value, which is the current iterator with every loop it makes (1, 2, 3 ... 100).


The do keyword catches this iterator, and uses it as the variable num.


Anytime you see the num variable, you are seeing the current iterator that's being returned by times.

How can I randomly iterate through a large Range?

I just remembered a similar problem from a class I took years ago; that is, iterating (relatively) randomly through a set (completely exhausting it) given extremely tight memory constraints. If I'm remembering this correctly, our solution algorithm was something like this:

1. Define the range to be from 0 to
   some number N
2. Generate a random starting point x[0] inside N
3. Generate an iterator Q less than N
4. Generate successive points x[n] by adding Q to
   the previous point and wrapping around if needed. That
   is, x[n+1] = (x[n] + Q) % N
5. Repeat until you generate a new point equal to the starting point.

The trick is to find an iterator that will let you traverse the entire range without generating the same value twice. If I'm remembering correctly, any relatively prime N and Q will work (the closer the number to the bounds of the range the less 'random' the input). In that case, a prime number that is not a factor of N should work. You can also swap bytes/nibbles in the resulting number to change the pattern with which the generated points "jump around" in N.

This algorithm only requires the starting point (x[0]), the current point (x[n]), the iterator value (Q), and the range limit (N) to be stored.

Perhaps someone else remembers this algorithm and can verify if I'm remembering it correctly?

How to iterate through mixed type array and return the first integer

You can use Enumerable#find

x.find {|s| s =~ /^\d+$/}
# => "111"

Ruby: Doing binary operations on bitstrings

You have Integer#to_s(base) and String.to_i(base) available to you.

a_and_b = (a.to_i(2) & b.to_i(2)).to_s(2)

a_or_b = (a.to_i(2) | b.to_i(2)).to_s(2)

What is a faster way to iterate through large numbers in Ruby?

You could use the prime factorization:

require 'prime'

def pp(n)
  pd = n.prime_division
  k = pd.map(&:last).reduce(&:gcd)
  return if k < 2
  m = pd.map { |p, e| p**(e / k) }.reduce(:*)
  [m, k]
end

For example for n = 216 you get [[2, 3], [3, 3]], meaning 216 = 2³⋅3³. Then find the greatest common divisor of the exponents, which is the greatest possible exponent k. If it's less than 2, you lose. Otherwise, compute the base m from the pieces.

Yours takes my PC about 4.1 seconds to check the numbers from 2 to 200. Mine takes about 0.0005 seconds for that, and takes about 2.9 seconds to check the numbers 2 to 400000.

Looping through an array with step

Ranges have a step method which you can use to skip through the indexes:

(0..array.length - 1).step(2).each do |index|
  value_you_care_about = array[index]
end

Or if you are comfortable using ... with ranges the following is a bit more concise:

(0...array.length).step(2).each do |index|
  value_you_care_about = array[index]
end

---

Related Topics