Using the algorithm in the reference
www.everything2.com/index.pl?node_id=449702 and the 'bitops' package, here
is some code that will select the numeric values with a specified number of
bits. It takes less than 12 seconds to select from 21-bit numbers. If I had
more memory, I would expect that for 25-bit numbers it would take about 200
seconds to compute the indices.
> mask1 <- 0x55555555
> mask2 <- 0x33333333
> mask4 <- 0x0f0f0f0f
> mask8 <- 0x00ff00ff
> mask16 <- 0x0000ffff
> require(bitops)
[1] TRUE
> x <- 0:(2^21 - 1) # test all number with 21 bits
> system.time({
+ x <- bitAnd(x, mask1) + bitAnd(bitShiftR(x, 1), mask1)
+ x <- bitAnd(x, mask2) + bitAnd(bitShiftR(x, 2), mask2)
+ x <- bitAnd(x, mask4) + bitAnd(bitShiftR(x, 4), mask4)
+ x <- bitAnd(x, mask8) + bitAnd(bitShiftR(x, 8), mask8)
+ x <- bitAnd(x, mask16) + bitAnd(bitShiftR(x, 16), mask16)
+ })
[1] 10.40 0.87 11.82 NA NA
> # print the first 10 numbers
> which(x == 9)[1:10] - 1 # account for sequence starting at zero
[1] 511 767 895 959 991 1007 1015 1019 1021 1022
On 5/13/06, Marc Schwartz <[EMAIL PROTECTED]> wrote:
>
> On Fri, 2006-05-12 at 15:35 -0500, Nameeta Lobo wrote:
> > Hi again
> >
> > Sorry I should have been more specific the first time. I am not actually
> trying
> > to generate this matrix but what am trying to do is to write a loop
> which takes
> > an input of 0000, does a bitwise addition, then checks to see if the new
> number
> > generated has two 1s(I just summed the values to get 2) and if it does
> outputs
> > that to a matrix. It goes on doing it till it reaches 1111.
> >
> > So my final output for the above would read
> > 0011
> > 0101
> > 0110
> > 1001
> > 1010
> > 1100
> >
> > For 2^6, I was looking for three 1s and so on.
> >
> > I wrote this in a for loop etc. Created the original matrix with
> expand.grid
> > command that you guys helped me out with before.
> >
> > My only concern was that for e.g. 2^25 or higher, not much space can be
> > allocated to the creation of the original matrix and then also because
> of the
> > loops there is the problem of computer time. So was just wondering if it
> was
> > easier to do it via bitwise addition.
> >
> > thanks a lot for your help everyone.
> >
> > any more suggestion!!!!
> >
> > nameeta
>
> Nameeta,
>
> This approach is still heavily time bound due to the process of
> comparing the resultant binary representations against the desired
> number of 1's. It is probably O(n^3) or worse.
>
> To improve on this, I suspect you will need to go to a compiled language
> such as C, where you can engage in more efficient bit level
> manipulations. Though perhaps somebody else here will have some further
> thoughts.
>
> My premise is that you are not just adding any number to 0, but are
> going in integer sequence from 0:((2^x) - 1) looking for a fixed number
> of 1's.
>
> Here is the code. It requires the use of Martin's digitsBase() function
> from package "sfsmisc" to create the binary representations of the
> integers.
>
>
> FindOnes <- function(exp, ones)
> {
> checkDigits <- function(x)
> {
> n <- digitsBase(x, ndigits = exp)
> if (sum(n) == ones)
> paste(n, collapse = "")
> }
>
> L <- sapply(1:((2^exp) - 1), checkDigits)
>
> do.call("rbind", L)
> }
>
>
> To use it:
>
> exp: The exponent desired, as in (2 ^ exp)
>
> ones: The number of 1's desired in the binary representation
>
>
> So for example:
>
> # Use 2^4 and get results with 2 1's
> # Took 0.004 seconds
> > FindOnes(4, 2)
> [,1]
> [1,] "0011"
> [2,] "0101"
> [3,] "0110"
> [4,] "1001"
> [5,] "1010"
> [6,] "1100"
>
>
> # 2^6 with 3 1's
> # Took 0.02 seconds
> > FindOnes(6, 3)
> [,1]
> [1,] "000111"
> [2,] "001011"
> [3,] "001101"
> [4,] "001110"
> [5,] "010011"
> [6,] "010101"
> [7,] "010110"
> [8,] "011001"
> [9,] "011010"
> [10,] "011100"
> [11,] "100011"
> [12,] "100101"
> [13,] "100110"
> [14,] "101001"
> [15,] "101010"
> [16,] "101100"
> [17,] "110001"
> [18,] "110010"
> [19,] "110100"
> [20,] "111000"
>
>
> Testing with 2^18 looking for 9 1's:
>
> > system.time(x <- FindOnes(18, 9))
> [1] 76.089 0.664 86.535 0.000 0.000
>
> > str(x)
> chr [1:48620, 1] "000000000111111111" "000000001011111111" ...
>
> > object.size(x)
> [1] 2722840
>
> I am curious as to your application here.
>
> HTH,
>
> Marc Schwartz
>
> ______________________________________________
> [email protected] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
--
Jim Holtman
Cincinnati, OH
+1 513 646 9390 (Cell)
+1 513 247 0281 (Home)
What is the problem you are trying to solve?
[[alternative HTML version deleted]]
______________________________________________
[email protected] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
