https://stackoverflow.com/questions/22169526
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianYes, 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)
}
}
is a number a power of 2
-
02-06-2023 - |
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.
Solution
OTHER TIPS
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
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
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.
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
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
