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.

Here's a list of algorithms: http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ and here's a question about C++ implementations, which could easily be setup with Rcpp: http://stackoverflow.com/questions/108318/whats-the-simplest-way-to-test-whether-a-number-is-a-power-of-2-in-c — Thomas, Mar 04 '14 at 10:47

score 6 · Accepted Answer · answered Mar 04 '14 at 11:43

6

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)
  }
}

answered Mar 04 '14 at 11:43

Scott Ritchie

10,293
3
28
64

Note though that `intToBits` doesn't complain if you give it say, a float `isPowerOf2(4.5)` – Scott Ritchie Mar 04 '14 at 11:46
2

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. – Carl Witthoft Mar 04 '14 at 12:22
@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`. – Mark Miller Mar 07 '14 at 18:51
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. – Mark Miller Mar 07 '14 at 19:13
1

@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`. – Carl Witthoft Mar 07 '14 at 22:04
@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)` – Mark Miller Mar 07 '14 at 22:07
@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`. – Mark Miller Mar 08 '14 at 01:30
@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. – Mark Miller Mar 08 '14 at 14:48
@MarkMiller posted. Pls move to "chat" if further questions. thanks – Carl Witthoft Mar 08 '14 at 21:33

Carl Witthoft · Answer 2 · 2014-03-08T22:11:28.197

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

score 2 · Answer 3 · answered Mar 04 '14 at 12:34

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

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');` — Mark Miller, Mar 07 '14 at 18:55

score 0 · Answer 4 · answered Mar 04 '14 at 11:49

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.

Well, you **should** be aware: `Rmpfr`, `gmp` , for example. — Carl Witthoft, Mar 04 '14 at 12:15

score 0 · Answer 5 · answered Mar 09 '14 at 08:05

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

score 0 · Answer 6 · answered Oct 30 '17 at 20:17

0

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.

answered Oct 30 '17 at 20:17

Omar Faroque Anik

2,531
1
29
42

R syntax should be different. – Omar Faroque Anik Nov 01 '17 at 00:47

is a number a power of 2

6 Answers6