How convert an integer to a bit array

[Curt Hibbs]

Does anyone have a clever way to convert an integer to an array of bit
values?

For example (using 8 bit integers):

0 => [0, 0, 0, 0, 0, 0, 0, 0]
1 => [0, 0, 0, 0, 0, 0, 0, 1]
2 => [0, 0, 0, 0, 0, 0, 1, 0]
7 => [0, 0, 0, 0, 0, 1, 1, 1]
etc.

I was looking at Array#pack and Array#unpack to do this, but haven't figured
it out yet. It just seems like there ought to be a simple way to do this.

Anybody got a clever idea?

Curt

[James Edward Gray II]

Does this help?

>> ("%b" % 5).split("").map { |n| n.to_i }
=> [1, 0, 1]

James Edward Gray II

[Joel VanderWerf]

s = ""
s[0] = 7
s.unpack("B*")[0].split("").map{|bit|bit.to_i}

=> [0, 0, 0, 0, 0, 1, 1, 1]

It should be easier than that, though.

--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

[Daniel Schüle]

irb(main):082:0> x = 7.to_s(2).split(//).map! {|bit| bit.to_i}
=> [1, 1, 1]
irb(main):083:0> x.unshift(0) until x.length == 8

if your number always fit into 8 bit
otherwise this doesn't work

Regards, Daniel

[Marcel Molina Jr.]

An alternative to ('%b' % n) is n.to_s(2)

marcel
--
Marcel Molina Jr. <mar...@vernix.org>

[Caleb Tennis]

>
>
> s = ""
> s[0] = 7
> s.unpack("B*")[0].split("").map{|bit|bit.to_i}
> => [0, 0, 0, 0, 0, 1, 1, 1]
>
>
>
> It should be easier than that, though.
>

How about:

num = 50

num.to_s(2).split("").map{ |bit| bit.to_i}

There's problably some trickery with String.each_with_index you can
do to make the map a little simpler.

[Marcel Molina Jr.]

You could do this:

x.unshift(0) until (x.size % 8).zero?

[Daniel Berger]

Nah, that's too much work.

x = ("%08d" % 7.to_s(2)).split('').map{ |e| e.to_i }

Replace 8 with the integer size and 7 with whatever number you're converting.

Regards,

Dan

[Ryan Leavengood]

This way is about 4 times faster than James' version:

class Integer
def to_ba(size=8)
a=[]
(size-1).downto(0) do |i|
a<<self[i]
end
a
end
end

p 0.to_ba
p 1.to_ba
p 2.to_ba
p 7.to_ba
__END__

Result:

[0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 1]

[0, 0, 0, 0, 0, 0, 1, 0]

[0, 0, 0, 0, 0, 1, 1, 1]

Ryan

[Ryan Leavengood]

On 11/22/05, Ryan Leavengood <leave...@gmail.com> wrote:
>
> This way is about 4 times faster than James' version:

For those curious:

----------------------------------------------------------------------
| QuickBench Session Started |
| 100000 Iterations |
----------------------------------------------------------------------
user system total real
1. 244.to_ba 1.171000 0.000000 1.171000 ( 1.172000)
2. ("%b" % 244).split(... 4.735000 0.000000 4.735000 ( 4.750000)
3. s.unpack("B*")[0].s... 4.156000 0.000000 4.156000 ( 4.156000)
4. 244.to_s(2).split("... 4.422000 0.000000 4.422000 ( 4.437000)
----------------------------------------------------------------------
| Fastest was <1. 244.to_ba> |
----------------------------------------------------------------------

QuickBench is a little script I wrote, which I may or may not release
into the wild.

The code will follow my name (note how I use the DATA section for the
things to benchmark):

Ryan "Mr. Benchmark" Leavengood

class Integer
def to_ba(size=8)
a=[]
(size-1).downto(0) do |i|
a<<self[i]
end
a
end
end

require 'quickbench'
s=" "
s[0]=244
QuickBench.go(100000, 22) {}
__END__
244.to_ba
("%b" % 244).split("").map { |n| n.to_i }

s.unpack("B*")[0].split("").map{|bit|bit.to_i}

244.to_s(2).split("").map{ |bit| bit.to_i}

[James Edward Gray II]

On Nov 22, 2005, at 4:23 PM, Curt Hibbs wrote:

Another thought: Ruby's Integers are already pretty close to a bit
Array. If you only need to index the bits, maybe it's best not to
convert at all...

James Edward Gray II

[James Edward Gray II]

On Nov 22, 2005, at 4:23 PM, Curt Hibbs wrote:

Last idea:

>> bits = Array.new(8) { |i| 7[i] }.reverse!

=> [0, 0, 0, 0, 0, 1, 1, 1]

I promise to stop spamming this thread now. ;)

James Edward Gray II

[Curt Hibbs]

You guys are awesome... so many good ideas here!

Thanks,
Curt

[Ryan Leavengood]

On 11/22/05, James Edward Gray II <ja...@grayproductions.net> wrote:
>
> >> bits = Array.new(8) { |i| 7[i] }.reverse!
> => [0, 0, 0, 0, 0, 1, 1, 1]

And the winner by a nose is.................................
..............................
..............................
James!!!

----------------------------------------------------------------------
| QuickBench Session Started |
| 300000 Iterations |

----------------------------------------------------------------------
user system total real

1. 244.to_ba 3.296000 0.015000 3.311000 ( 3.313000)
2. Array.new(8) { |i| ... 2.782000 0.000000 2.782000 ( 2.781000)
----------------------------------------------------------------------
| Fastest was <2. Array.new(8) { |i| ...> |
----------------------------------------------------------------------

I'm glad you posted this because it is elegant and fast. OK, now I'll
stop spamming this thread with benchmark results :)

Regards,
Ryan

[Curt Hibbs]

On 11/23/05, Ryan Leavengood <leave...@gmail.com> wrote:
>
> On 11/22/05, James Edward Gray II <ja...@grayproductions.net> wrote:
> >
> > >> bits = Array.new(8) { |i| 7[i] }.reverse!
> > => [0, 0, 0, 0, 0, 1, 1, 1]
>
> And the winner by a nose is.................................
> ...............................

> ...............................

> James!!!
>
> ----------------------------------------------------------------------
> | QuickBench Session Started |
> | 300000 Iterations |
> ----------------------------------------------------------------------
> user system total real
> 1. 244.to_ba 3.296000 0.015000 3.311000 ( 3.313000)
> 2. Array.new(8) { |i| ... 2.782000 0.000000 2.782000 ( 2.781000)
> ----------------------------------------------------------------------
> | Fastest was <2. Array.new(8) { |i| ...> |
> ----------------------------------------------------------------------
>
> I'm glad you posted this because it is elegant and fast. OK, now I'll
> stop spamming this thread with benchmark results :)
>

Cool! Thanks for doing the benchmark.

Curt

[Ed Howland]

On 11/23/05, Curt Hibbs <curt....@gmail.com> wrote:
> On 11/23/05, Ryan Leavengood <leave...@gmail.com> wrote:
> >
> > On 11/22/05, James Edward Gray II <ja...@grayproductions.net> wrote:
> > >
> > > >> bits = Array.new(8) { |i| 7[i] }.reverse!
> > > => [0, 0, 0, 0, 0, 1, 1, 1]
> >
> > And the winner by a nose is
..

> > James!!!
> >

def to_ba(num, size=8)
(-size+1..0).inject({}) {|x,i| x << num[-i]}
end

to_ba(15)
=> [0,0,0,0,1,1,1,1]

It may be a tad faster, the bigger the array, due to the lack of
reverse. Can someone bench it? I don't have require 'quickbench'

Or perhaps, modifying James':

def to_ba(num, size=8)
Array.new(size) {|i| num[-i+size-1]}
end

Ed

[Daniel Sheppard]

>> bits = Array.new(8) { |i| 7[i] }.reverse!

This code will call:
Integer#[] 8 times
Array.new once
Array.reverse! once

> def to_ba(num, size=8)
> (-size+1..0).inject({}) {|x,i| x << num[-i]} end

This code will call:
Integer#[] 8 times
Array.new twice

Range.new once
Integer#@- once
Integer#+ once
Array#inject once
Array#<< 8 times

All those calls are slower than the single call to Array.reverse!

> Or perhaps, modifying James':
>
> def to_ba(num, size=8)
> Array.new(size) {|i| num[-i+size-1]}
> end

Integer#[] 8 times
Array.new once

Integer#@- 8 times
Integer#+ 8 times
Integer#- 8 times

Once again, those extra calls take longer than the single call to
Array#reverse!.

It's an easy trap to fall into - experience in most other languages
teaches you that simple operations on primitives are much faster than
calling of to a method. The problem with porting that knowledge to ruby
is that there are not operations on primitives - everything is going
through the method dispatching.

I believe most (all?) of the methods above are implemented in C - best
thing you can do for your code is to make it faster is to spend the
least amount of time possible in ruby-land - in 99% of situations, one
call to C code will outperform anything that takes more than 1 call to
get to C code (it's only if the algorithm in the C code is drastically
bad that you'll be able to outperform it, and I trust that ruby's code
core contains no algorithms that bad).

24 calls through the message dispatching or 1 call through message
dispatching - it's easy to see the speed improvement.

Benchmark.bm(10) {|bm|
bm.report('james') {100000.times {Array.new(8) { |i| 7[i] }.rev
bm.report('ed1') {100000.times {(-8+1..0).inject([]) {|x,i| x <<
7[-i]}}}
bm.report('ed2') {100000.times {Array.new(8) {|i| 7[-i+8-1]}}}
}
user system total real
james 0.781000 0.000000 0.781000 ( 0.781000)
ed1 2.859000 0.000000 2.859000 ( 2.922000)
ed2 1.219000 0.000000 1.219000 ( 1.250000)

#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################

[Ed Howland]

On 11/23/05, Daniel Sheppard <dan...@pronto.com.au> wrote:
> Integer#[] 8 times
> Array.new once
>
> Integer#@- 8 times
> Integer#+ 8 times
> Integer#- 8 times
>
> Once again, those extra calls take longer than the single call to
> Array#reverse!.
>
> It's an easy trap to fall into - experience in most other languages
> teaches you that simple operations on primitives are much faster than
> calling of to a method. The problem with porting that knowledge to ruby
> is that there are not operations on primitives - everything is going
> through the method dispatching.
>

...

I saw that you were right. I used require 'benchmark' and 100,000 and
1M size arrays. I guess I was assuming, as you say, that my
optimization to primative operations ((-), and +) would be faster, but
in fact actually increased the amount of time in Ruby land.

Thanks for the insight. What makes that great, is the knowledge that
writing code the way you think about a problem, may in fact be the
ultimate solution.

Ed