Select all binary neighbors of a decimal number

Question

Select all binary neighbors of a decimal number

Let's say I have a number in decimal format: 5

its binary version: 00101

I would like to write a function that takes a decimal number x

and returns all other decimal numbers that have a difference of one digit (in binary forms) from the original:

so for the example above neighbors:

10101 01101 00111 00001 00100

and the corresponding decimal places:

21 13 7 1 4

I would like the solution to be computationally efficient and not time consuming, even if I say a million digits.

Can this be done?

+3

decimal binary r

user1984076 28 june 15 at 19:08

source to share

3 answers

I don't know how the trial and error got me here, but it looks valid unless I mess up the binaries and decimals:

bin_neighs = function(x, n) bitwXor(x, (2 ^ (0:(n - 1))))
bin_neighs(5, 5)
#[1]  4  7  1 13 21

+10

alexis_laz 28 june 15 at 20:15

source to share

Here's another way to use magrittr

pipe:

binNeighbours <- function(a, numNeighbours = ceiling(log2(a))) {
    rep(a, numNeighbours) %>%
    outer(., seq(.) - 1, function(x, y) x %/% (2 ^ y) %% 2) %>%
    `diag<-`(., 1 - diag(.)) %>%
    `%*%`(2 ^(0:(nrow(.) - 1))) %>%
    `[`(, 1)
  }

+1

Nick kennedy 28 june 15 at 20:25

source to share

josliber · Accepted Answer · 2015-06-28T19:32:22+0000

I think you are asking how to take the number 5 as input and return all adjacent binary values. To do this, you need to convert the number to a useful binary format (just the bit you want to flip), flip each bit, and return the result:

library(R.utils)
bin.neighbors <- function(x, num.neighbors=NA) {
  # Get the bits with the appropriate amount of padding
  bits <- as.numeric(unlist(strsplit(intToBin(x), "")))
  if (!is.na(num.neighbors) & num.neighbors > length(bits)) {
    bits <- c(rep(0, num.neighbors-length(bits)), bits)
  }

  # Build a matrix where each column is a bit vector of a neighbor
  mat <- matrix(bits, length(bits), length(bits))
  diag(mat) <- 1-diag(mat)

  # Return the decimal values of the neighbors using strtoi
  apply(mat, 2, function(x) strtoi(paste0(x, collapse=""), 2))
}
bin.neighbors(5, 5)
# [1] 21 13  1  7  4

Since each number has multiple binary representations with different leading 0 numbers (for example, 5 can be represented as 101, 0101, 00101, 000101, 0000101, etc.), I added an argument num.neighbors

to indicate the length from the output vector from the function. You can pass NA to get an output vector equal to the number of bits in the binary representation of the input, without leading zeros.

Select all binary neighbors of a decimal number

More articles: