Select all binary neighbors of a decimal number that differ by exactly n digits
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 with the difference of digits n
(in binary forms) from the original:
so for the example above, if n
there is 2
, then I search for all neighbors 00101
that differ in exactly numbers n=2
.
And then I want to get the decimal places corresponding to these binary neighbors.
Can this be done?
To get one digitally neighbors I can use:
bin_neighs = function(x, n) bitwXor(x, (2 ^ (0:(n - 1))))
My question is, how can I generalize this from one digit neighborhood to n digit neighbors?
source to share
You can generalize this by finding all the bitmasks with the desired length and number of digits, and then doing a bitwise xor:
bin_neighs <- function(x, nf, n) {
bitwXor(x, colSums(combn(2^(0:(n-1)), nf)))
}
bin_neighs(5, 2, 5)
# [1] 6 0 12 20 3 15 23 9 17 29
We can confirm that this is correct by using the binary decomposition of x = 5 to n = 5 digits: 00101. Inverting nf = 2 digits gives the following possibilities:
00110 = 6 # Flip 4 and 5
00000 = 0 # Flip 3 and 5
01100 = 12 # Flip 2 and 5
10100 = 20 # Flip 1 and 5
00011 = 3 # Flip 3 and 4
01111 = 15 # Flip 2 and 4
10111 = 23 # Flip 1 and 4
01001 = 9 # Flip 2 and 3
10001 = 17 # Flip 1 and 3
11101 = 29 # Flip 1 and 2
This should also work efficiently for slightly larger inputs. For example, it can flip 9 out of 15 bits in less than 10 milliseconds:
library(microbenchmark)
microbenchmark(bin_neighs(1,9,15))
# Unit: milliseconds
# expr min lq mean median uq max neval
# bin_neighs(1, 9, 15) 7.472961 8.023485 8.848333 8.237502 8.594779 33.61931 100
source to share