3

I have the question similar to What's the fastest method to return the position of the least significant bit set in an integer in Python 3? , finding the first set bit in a binary number , and Position of least significant bit that is set for R. I need to find the position of the least significant set bit in an integer in R. The solution proposed by Spätzle is the following:

unlist(lapply(x, function(z) min(which(as.integer(intToBits(z)) == 1))-1))

Are there more efficient ways to do it?

Viktor
  • 472
  • 5
  • 14

2 Answers2

4

The following is much faster:

f <- function(x){
  log2(bitwAnd(x,-x))
}

For comparison:

g <- function(x){
  unlist(lapply(x, function(z) min(which(as.integer(intToBits(z)) == 1))-1))
}

A quick test:

> library(microbenchmark)
> tests <- floor(runif(1000,1,2^31))
> sum(f(tests) == g(tests)) #just to check
[1] 1000
> microbenchmark(f(tests),g(tests))
Unit: microseconds
     expr      min        lq       mean   median        uq       max neval
 f(tests)   38.435   40.5515   45.82673   42.667   45.1355   146.337   100
 g(tests) 1985.940 2083.9680 2530.79036 2131.218 2287.4280 11749.204   100
John Coleman
  • 51,337
  • 7
  • 54
  • 119
3

If you have long vectors and want to go to C++ then the following code might help you (together with Rcpp and the ffs function from strings.h):

#include <Rcpp.h>
#include <strings.h>
using namespace Rcpp;

// [[Rcpp::export]]
Rcpp::IntegerVector lsb(const IntegerVector x)
{
  IntegerVector res(x.size());
  std::transform(x.begin(), x.end(), res.begin(), ffs);
  return(res-1);  # To start from 0
}

Save the code above as a file, say lsb.cpp, and compile it using sourceCpp("lsb.cpp") from the Rcpp package.

It is slightly faster - at least for longer input vectors where the overhead becomes negligible

> x <- floor(runif(10000,1,2^31))
> microbenchmark::microbenchmark(f(x), g(x), lsb(x))
Unit: microseconds
   expr       min         lq        mean    median         uq       max neval
   f(x)   121.771   129.6360   168.91273   133.241   151.0110  1294.667   100
   g(x) 36165.757 40508.1740 50371.45183 42608.686 60460.5270 94664.255   100
 lsb(x)    25.767    26.8015    34.58856    33.035    35.2385   156.852   100
ekstroem
  • 5,957
  • 3
  • 22
  • 48