Ruby - get bit range from variable

Question

I have a variable and want to take a range of bits from that variable. I want the CLEANEST way to do this.

If x = 19767 and I want bit3 - bit8 (starting from the right): 100110100110111 is 19767 in binary. I want the part in parenthesis 100110(100110)111 so the answer is 38.

What is the simplest/cleanest/most-elegant way to implement the following function with Ruby?

bit_range(orig_num, first_bit, last_bit)

PS. Bonus points for answers that are computationally less intensive.

So you don't want to learn binary and use ANDs and SHIFTs like us veterans? Huh. Kids these days. :-) — the Tin Man
– the Tin Man, Commented Nov 8, 2012 at 23:08
You should accept @DigitalRoss's answer then as he's showing both a String based solution, along with pure bit twiddling. Don't reject using to_s(2) though, it can short-circuit a lot of messy shifting and ANDing. — the Tin Man
– the Tin Man, Commented Nov 9, 2012 at 14:43
I'll accept an answer, don't worry. I'm not a stack-overflow slacker. I'm confused about your second sentance, Digital Ross's second answer has no to_s(2) and it is not messy. — Selah
– Selah, Commented Nov 9, 2012 at 15:17
Comments to @texasbruce's answer wanted a non-to_s(2) solution. There's a lot to be said for using to_s(2) string manipulation, though it gives up a little speed as it can greatly simply the twiddling. — the Tin Man
– the Tin Man, Commented Nov 9, 2012 at 15:24

DigitalRoss · Accepted Answer · 2012-11-09 15:27:27Z

3

19767.to_s(2)[-9..-4].to_i(2)

or

19767 >> 3 & 0x3f

Update:

Soup-to-nuts (why do people say that, anyway?) ...

class Fixnum
  def bit_range low, high
    len = high - low + 1
    self >> low & ~(-1 >> len << len)
  end
end

p 19767.bit_range(3, 8)

edited Nov 9, 2012 at 15:27

answered Nov 8, 2012 at 22:35

DigitalRoss

147k25 gold badges255 silver badges336 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Selah Over a year ago

i like the second one because it doesn't require string conversion, but is there a way to make it more general, so I could input any starting bit and any ending bit

the Tin Man Over a year ago

Sure there's ways to do it, but we expect you to figure that sort of thing out. It's simply substituting variables for values you've calculated. Think of what 0x3f looks in binary, along with what >> 3 is doing.

Selah Over a year ago

I guess I could substitute 0x3f with 2^(high_bit)-1 ??

DigitalRoss Over a year ago

@Selah .. well, the Tin Man is right, but I had the idea of monkey-patching Fixnum and could not resist showing you the whole answer. I hope you like it. BTW, I answered the Q as asked, but I would suggest reversing the order of low, high to high, low.

the Tin Man Over a year ago

Adding bit_range strikes a nice balance with readability and speed. Well done, as usual. :-)

SwiftMango · Accepted Answer · 2012-11-08 22:34:35Z

3

orig_num.to_s(2)[(-last_bit-1)..(-first_bit-1)].to_i(2)

answered Nov 8, 2012 at 22:34

SwiftMango

15.4k14 gold badges79 silver badges140 bronze badges

3 Comments

Gregory Brown Over a year ago

This is a nice solution, but I wonder if there is a clean way to do this task without converting to a string and back...

SwiftMango Over a year ago

@GregoryBrown you cant really do bitwise shift because selecting a range requires shifting both right and left, and the boundary for shifting left in Ruby is .. Eh unknown.

Gregory Brown Over a year ago

Good point. I was sort of hoping that because you can do original_num[index], that original_num[start..end] would work, but unfortunately that's not supported ;-)

Simon Perepelitsa · Accepted Answer · 2012-11-09 14:59:47Z

2

Here is how this could be done using pure number operations:

class Fixnum
  def slice(range_or_start, length = nil)
    if length
      start = range_or_start
    else
      range = range_or_start
      start = range.begin
      length = range.count
    end

    mask = 2 ** length - 1

    self >> start & mask
  end
end

def p n
  puts "0b#{n.to_s(2)}"; n
end

p 0b100110100110111.slice(3..8) # 0b100110
p 0b100110100110111.slice(3, 6) # 0b100110

answered Nov 9, 2012 at 14:59

Simon Perepelitsa

20.7k8 gold badges58 silver badges75 bronze badges

5 Comments

the Tin Man Over a year ago

Please don't edit my answer with the results of running the benchmark for your code on your machine. Machines vary in speed, so if you feel your algorithm wasn't running at its full speed feel free to copy the benchmark code, run it on your machine, and put the full results into your answer. Doing otherwise could result in misleading values.

Simon Perepelitsa Over a year ago

I have copied the full benchmark results of course. From your comment I thought you were fine with me running the new benchmark on my machine.

the Tin Man Over a year ago

I'm fine with you running it, just don't modify the results I show. You could add your results to your answer, or have appended them to mine. Overwriting mine is different.

Simon Perepelitsa Over a year ago

Sorry, I misunderstood your "beat you to it". The point of my solution is not in speed, but I thought your answer might be better with a second usage. Anyway, I'm leaving that up to you.

Selah Over a year ago

thanks semyon, this answer is good, wish I could check two answers

the Tin Man · Accepted Answer · 2012-11-09 15:36:50Z

2

Just to show the speeds of the suggested answers:

require 'benchmark'

ORIG_NUMBER = 19767

def f(x,i,j)
  b = x.to_s(2)
  n = b.size
  b[(n-j-1)...(n-i)].to_i(2)
end

class Fixnum
  def bit_range low, high
    len = high - low + 1
    self >> low & ~(-1 >> len << len)
  end

  def slice(range_or_start, length = nil)
    if length
      start = range_or_start
    else
      range = range_or_start
      start = range.begin
      length = range.count
    end

    mask = 2 ** length - 1

    self >> start & mask
  end
end

def p n
  puts "0b#{n.to_s(2)}"; n
end

n = 1_000_000
puts "Using #{ n } loops in Ruby #{ RUBY_VERSION }."
Benchmark.bm(21) do |b|
  b.report('texasbruce') { n.times { ORIG_NUMBER.to_s(2)[(-8 - 1)..(-3 - 1)].to_i(2) } }
  b.report('DigitalRoss string') { n.times { ORIG_NUMBER.to_s(2)[-9..-4].to_i(2) } }
  b.report('DigitalRoss binary') { n.times { ORIG_NUMBER >> 3 & 0x3f } }
  b.report('DigitalRoss bit_range') { n.times { 19767.bit_range(3, 8) } }
  b.report('Philip') { n.times { f(ORIG_NUMBER, 3, 8) } }
  b.report('Semyon Perepelitsa') { n.times { ORIG_NUMBER.slice(3..8) } }
end

And the output:

Using 1000000 loops in Ruby 1.9.3.
                            user     system      total        real
texasbruce              1.240000   0.010000   1.250000 (  1.243709)
DigitalRoss string      1.000000   0.000000   1.000000 (  1.006843)
DigitalRoss binary      0.260000   0.000000   0.260000 (  0.262319)
DigitalRoss bit_range   0.840000   0.000000   0.840000 (  0.858603)
Philip                  1.520000   0.000000   1.520000 (  1.543751)
Semyon Perepelitsa      1.150000   0.010000   1.160000 (  1.155422)

That's on my old MacBook Pro. Your mileage might vary.

edited Nov 9, 2012 at 15:36

answered Nov 9, 2012 at 14:57

the Tin Man

161k44 gold badges222 silver badges308 bronze badges

2 Comments

Simon Perepelitsa Over a year ago

Nice :-) You should add an example with length too: ORIG_NUMBER.slice(3, 6)

SwiftMango Over a year ago

No DigitalRose 's solutions does not contain variables. Its all constants so surly its faster.

Philip · Accepted Answer · 2012-11-08 22:39:38Z

1

Makes sense to define a function for that:

def f(x,i,j)
  b = x.to_s(2)
  n = b.size
  b[(n-j-1)...(n-i)].to_i(2)
end

puts f(19767, 3, 8) # => 38

answered Nov 8, 2012 at 22:39

Philip

3,5207 gold badges32 silver badges42 bronze badges

1 Comment

Selah Over a year ago

nice, thanks for actually defining a function. is there a way to do it without converting to strings though??

bashaus · Accepted Answer · 2014-12-27 09:39:55Z

0

Expanding on the idea from DigitalRoss - instead of taking two arguments, you can pass a range:

class Fixnum
  def bit_range range
    len = range.last - range.first + 1
    self >> range.first & ~(-1 >> len << len)
  end
end

19767.bit_range 3..8

answered Dec 27, 2014 at 9:39

bashaus

1,7132 gold badges17 silver badges35 bronze badges

Collectives™ on Stack Overflow

Ruby - get bit range from variable

6 Answers 6

5 Comments

3 Comments

5 Comments

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

5 Comments

3 Comments

5 Comments

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related