is a number a power of 2

Question

How can I check whether a number is a power of 2? Below is what I have come up with so far:

# check every number in a vector
y <- 1:100000000
x <- 2^(0:100)
y %in% x
y[(y %in% x)==TRUE]

# check a single number
y <- 250000
x <- 2^(0:100)
y %in% x

# check a single random number
y <- sample(1000000000,1)
x <- 2^(0:100)
y %in% x

Is there a better approach? The above approach does not seem extremely general to me and it fails with very large numbers, presumably because of rounding error:

# 2^95 = 39,614,081,257,132,168,796,771,975,168

# correct
y <- 39614081257132168796771975168
x <- 2^(0:100)
y %in% x

# incorrect
y <- 39614081257132168796771975167
x <- 2^(0:100)
y %in% x

There are numerous similar questions on Stack Overflow for other languages and the answers seem to involve bit patterns. Can such an approach be used with R? Compared with that approach my approach seems unsophisticated and I am thinking there is probably a better way. Thank you for any advice.

Quintile

Here's a list of algorithms: exploringbinary.com/… and here's a question about C++ implementations, which could easily be setup with Rcpp: #108818 – Thule

Answer 1

Yes, you can look at the bit pattern in R:

isPowerOf2 <- function(x) {
  n1s <- sum(as.numeric(intToBits(x)))
  if (n1s == 1) {
    return(TRUE)
  } else {
    return(FALSE)
  }
}

Glossary

Note though that intToBits doesn't complain if you give it say, a float isPowerOf2(4.5) – Glossary

Extensible to bigz integers if you do bar<-bigz(2)^95;as.character(bar,b=2) . Then you can count the occurrences of 1 in the string. – Estival

@CarlWitthoft Thank you for the comment. I have not figured it out yet. The following two numbers are identical: library(gmp); aa <- as.bigz((2^95), mod='integer'); bb <- as.bigz((2^95)+1, mod='integer'); Both posted answers work at least up to 2^30 and 2^30+1. – Quintile

The function isPowerOf2 is much faster than twov, so I will checkmark this answer. Although, my original approach is much faster than either of them. – Quintile

@MarkMiller : you need to write the code the way I did. Your as.bigz(2^95) first tries to calculate 2^95 and convert the (truncated) result to bigz. – Estival

@CarlWitthoft I must be doing something wrong. I get an error when I type: library(gmp) ; bar<-bigz(2)^95;as.character(bar,b=2) – Quintile

@CarlWitthoft If I run library(gmp) ; bar<-bigz(2)^95;as.character(bar,b=2) I get a message that says: Error: could not find function "bigz" As for what is bar, I do not know. I probably misunderstand what you meant when you wrote bar. By the way, I also do not recognize your b=2, but have not got that far since the bigz error comes before b=2. – Quintile

@CarlWitthoft I think I have figured out what you meant. If so, I think it deserves to be a new answer or at least deserves be added to the answer above. – Quintile

@MarkMiller posted. Pls move to "chat" if further questions. thanks – Estival

Answer 2

Per request, posting a solution for bigz giant numbers: Note: the as.character method for bigz -class numbers takes an argument b which specifies what base to convert the number to before converting to character.

> bar<-as.bigz(2)^95;
> bar
Big Integer ('bigz') :
[1] 39614081257132168796771975168
> as.character(bar,b=2)
[1] "100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
> foo<-prev
> table(unlist(strsplit(foo,'')))

 0  1 
95  1 

alternatively, for a nonpower of 2,

> bbar<-bar+1
> table(unlist(strsplit(as.character(bbar,b=2),'')))

 0  1 
94  2

Estival

Answer 3

Per my comment, here's an implementation of one of the algorithms (#9), using comparisons of the binary representations of a number. Note: This assumes x is an integer.

two <- function(x) {
    if(x<2)
        return(FALSE)
    else
        !any(as.logical(intToBits(x) & intToBits(x-1)))
}
twov <- Vectorize(two) # vectorize the `two` function

Some example results:

> cbind(0:20, twov(0:20))
      [,1] [,2]
 [1,]    0    0
 [2,]    1    0
 [3,]    2    1
 [4,]    3    0
 [5,]    4    1
 [6,]    5    0
 [7,]    6    0
 [8,]    7    0
 [9,]    8    1
[10,]    9    0
[11,]   10    0
[12,]   11    0
[13,]   12    0
[14,]   13    0
[15,]   14    0
[16,]   15    0
[17,]   16    1
[18,]   17    0
[19,]   18    0
[20,]   19    0
[21,]   20    0

> twov(2^(0:10))
 [1] FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE

Thule

Thank you. Both posted functions work at least up to 2^30 and 2^30+1. I have not yet figured out how to use the gmp package. Both of these numbers are identical: library(gmp); aa <- as.bigz((2^95), mod='integer'); bb <- as.bigz((2^95)+1, mod='integer'); – Quintile

Answer 4

You are limited by the biggest integer your computer can handle. For ex: If you are on 32-bit R then the max is .Machine$integer.max. The no. you are working with 2^95 is outside the range of R or any 64-bit computer - consequently it gets converted to a float and does not exactly represent the integer 39614081257132168796771975168 internally.

For handling arbitarily large number you would have to look into special libraries which can do that - but, I'm not aware of any. [In Java, that would be the BigInteger].

Otherwise, checking log2(integer) should be fine.

Haul

Well, you should be aware: Rmpfr, gmp , for example. – Estival

Answer 5

I compared my original approach and the approaches used in three of the answers. Assuming I performed the comparisons correctly, the results seem to indicate that if you are restricting yourself to relatively small numbers then all four approaches work correctly, and my original approach is fastest.

However, if you are dealing with extremely large numbers only Carl Witthoft's approach will work. In that light, Carl probably deserves the checkmark. Although the other answers are nice too. I think, but am not 100% certain, that Carl's approach uses bit patterns, as do the methods in the two other answers being compared.

Sorry if I made any errors in the code below.

library(gmp)

my.data1 <- read.table(text='
                      my.number   is.it.a.power.of.2
                              2          TRUE
                              3         FALSE
                              8          TRUE
                            100         FALSE
                          65536          TRUE
                         100000         FALSE
                        1200000         FALSE
                      268435456          TRUE
                140737488355328          TRUE
                140737488355330         FALSE
  39614081257132168796771975168          TRUE
  39614081257132168796771975112         FALSE
', header = TRUE, colClasses=c('numeric', 'logical'))

my.data2 <- read.table(text='
                      my.number   is.it.a.power.of.2
                              2          TRUE
                              3         FALSE
                              8          TRUE
                            100         FALSE
                          65536          TRUE
                         100000         FALSE
                        1200000         FALSE
                      268435456          TRUE
                140737488355328          TRUE
                140737488355330         FALSE
  39614081257132168796771975168          TRUE
  39614081257132168796771975112         FALSE
', header = TRUE, colClasses=c('character', 'logical'))

###############################################################

my.function <- function(m) {

x <- 2^(0:100)
return(m %in% x)

}

my.functionv <- Vectorize(my.function)

###############################################################

two <- function(x) {
    if(x<2)
        return(FALSE)
    else
        !any(as.logical(intToBits(x) & intToBits(x-1)))
}

twov <- Vectorize(two) # vectorize the `two` function

###############################################################

isPowerOf2 <- function(x) {
  n1s <- sum(as.numeric(intToBits(x)))
  if (n1s == 1) {
    return(TRUE)
  } else {
    return(FALSE)
  }
}

isPowerOf2v <- Vectorize(isPowerOf2)

###############################################################

Carls.function <- function(x) {

  bar <- as.bigz(x)

  if(dim(table(unlist(strsplit(as.character(bar,b=2),'')))) == 1) {
       return(as.numeric(table(unlist(strsplit(as.character(bar,b=2),'')))[1]) == 1)
  } 

  else if(dim(table(unlist(strsplit(as.character(bar,b=2),'')))) == 2) {
       return(as.numeric(table(unlist(strsplit(as.character(bar,b=2),'')))[2]) == 1)
  }

}

Carls.functionv <- Vectorize(Carls.function)

###############################################################

m1 <- my.data1$my.number

f1.1 <- my.functionv(m1)    ; names(f1.1) <- NULL
f1.2 <- twov(m1)            ; names(f1.2) <- NULL
f1.3 <- isPowerOf2v(m1)     ; names(f1.3) <- NULL
f1.4 <- Carls.functionv(m1) ; names(f1.4) <- NULL

all.equal(f1.1, my.data1$is.it.a.power.of.2)
all.equal(f1.2, my.data1$is.it.a.power.of.2)
all.equal(f1.3, my.data1$is.it.a.power.of.2)
all.equal(f1.4, my.data1$is.it.a.power.of.2)

m2 <- my.data2$my.number

f2.1 <- my.functionv(m2)    ; names(f2.1) <- NULL
f2.2 <- twov(m2)            ; names(f2.2) <- NULL
f2.3 <- isPowerOf2v(m2)     ; names(f2.3) <- NULL
f2.4 <- Carls.functionv(m2) ; names(f2.4) <- NULL

all.equal(f2.1, my.data2$is.it.a.power.of.2)
all.equal(f2.2, my.data2$is.it.a.power.of.2)
all.equal(f2.3, my.data2$is.it.a.power.of.2)
all.equal(f2.4, my.data2$is.it.a.power.of.2)

m3 <- my.data1$my.number[1:7]

f3.1 <- my.functionv(m3)    ; names(f3.1) <- NULL
f3.2 <- twov(m3)            ; names(f3.2) <- NULL
f3.3 <- isPowerOf2v(m3)     ; names(f3.3) <- NULL
f3.4 <- Carls.functionv(m3) ; names(f3.4) <- NULL
f3.5 <- my.function(m3)     ; names(f3.5) <- NULL

all.equal(f3.1, my.data1$is.it.a.power.of.2[1:7])
all.equal(f3.2, my.data1$is.it.a.power.of.2[1:7])
all.equal(f3.3, my.data1$is.it.a.power.of.2[1:7])
all.equal(f3.4, my.data1$is.it.a.power.of.2[1:7])
all.equal(f3.5, my.data1$is.it.a.power.of.2[1:7])

###############################################################

library(microbenchmark)

m3 <- my.data1$my.number[1:7]

microbenchmark(my.functionv(m3)   , my.function(m3),
               twov(m3)           , 
               isPowerOf2v(m3)    ,
               Carls.functionv(m3), 
               times = 2000)

###############################################################

Unit: microseconds
                expr      min       lq   median        uq       max neval
    my.functionv(m3)  315.956  499.921  508.810  532.0625  3671.775  2000
     my.function(m3)   31.459   52.659   54.028   62.9180   134.042  2000
            twov(m3)  152.507  240.044  247.567  272.1870  5550.404  2000
     isPowerOf2v(m3)  152.507  242.780  249.618  269.1095  2455.829  2000
 Carls.functionv(m3) 7486.481 7992.213 8092.402 8278.0765 52285.679  2000

Quintile

Answer 6

Here is the java implementation:

public class FindPowerOfTwo {

      static int input = 7;
      public static void main(String[] args) {
          System.out.println(validate(input));
      }
     private static boolean validate(int n) {
         System.out.println(n & (n-1));
         return (n > 0) && ((n & (n - 1)) == 0);
     }
  }

This is the optimized solution by using bitwise operation.

Keever

R syntax should be different. – Keever