[R] bitwise addition

[Marc Schwartz]

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