Finding smallest symmetric binary roots of a number

An integer obtained by reversing bits of a given integer A is denoted as `bit-rev(A)`. For example, `bit-rev(25) = 19`, because binary represenation of `25` is `11001` and after reversing it becomes `10011`, i.e. `19`. Furthermore, `bit-rev(26) = 11` and `bit-rev(11) = 13`. A symmetric binary root of a given positive integer `N` is a positive integer A such that `N=A*bit-rev(A)`. For example symmetric binary root of `50` is `10`, because `10*bit-rev(10)=10*5=50` . Note that `5` is not a symmetric binary root of `50`. Number `286` has two symmetric binary roots: `22` and `26`. Write a function

``````int symmetric_binary_root_count(in​t n)
``````

that given a positive integer N returns the smallest symmetric binary root of N. The function should return -1 if N doesn't have any symmetric binary root. Assume that 0

If you like you can use this function for bit-rev (JavaScript):

``````function bit_rev(n){
var x = n.toString(2).toString(),
arr = [];
for(var i = 0; i< x.length; i++){ arr.push(x.substr(i,1));}
x = arr.reverse().join('');
return parseInt(x,2);
}
``````
-
`Array.prototype.split` is a better alternative than your `for-loop`. – Thomas Eding Aug 15 '11 at 23:28
`Àssume that 0` - that 0 ...? And what is the challenge? You even provide a bitrev-method for javascript. – user unknown Aug 15 '11 at 23:31
@trinithis I'm filling array not splitting – Mohsen Aug 15 '11 at 23:39
The challenge is finding the smallest semantic binary root. It's kind of running function in reverse side or finding f(x) from x – Mohsen Aug 15 '11 at 23:42
I think I can prove that `min_symmetric_binary_root(2n) = 2 min_symmetric_binary_root(n)`, which allows reducing the problem to finding the minimum symmetric binary root of odd numbers. Since an odd number bit-reverses to an odd number of the same length, this allows working out from the square root and stopping when you pass a power of two. – Peter Taylor Aug 16 '11 at 7:40

Scala:

``````def bitrev (n: Int) =
Integer.parseInt (n.toBinaryString.reverse, 2)

def symmetricBinaryRootCount (n: Int) =
(1 to n).find (i=> i * bitrev (i) == n)

def sbrc (n: Int) =
symmetricBinaryRootCount (n) match {
case Some (n: Int) => n
case None          => -1
}

sbrc (50)
sbrc (286)
``````

results in 10, 22. Pretty straight forward. No golfing?

update, explaining the code.

sbrc (50) is the invocation - result is 10. sbrc (50) calls the so named method (def ...) above, which takes an int, and passes it to symmetricBinaryRootCount. The result is matched against two cases, Some (Int) or None, which are the result of `find` (which we will see later).

Scala has a Type Option, which is parametric, like List or Array, so you can have an Option [Int] or an Option[Array[String]] and so on. The content of the Option is either None or Some - Some Int, Some Array of String. In other languages the name is Maybe, and the purpose is, to avoid NullPointerExceptions.

So depending on the result, we return the result or we return -1, if there is no result. The result is produced by this method:

``````def symmetricBinaryRootCount (n: Int) =
(1 to n).find (i=> i * bitrev (i) == n)
``````

(1 to n) is simply the range of 1 to n. In this range find something, which is a true expression.
find iterates over the range, and tries 1, 2, 3, ... as i in the expression (i * bitrev (i) == n).

And bitrev is made from library methods and implicit conversions:

``````Integer.parseInt (n.toBinaryString.reverse, 2)
``````

10.toBinaryString is "1010".
"1010"reverse is "0101"
Integer.parseInt ("0101", 2) parses the input as Base-2 encoded String.

So bitrev(10) is 5, and 10 * bitrev(10) = 50 will be the first solution found in (1 to 50).

Find operates lazy, that means it will stop after finding a result and not probing teh values from 11 to 50.

And here is a pre-golfed one-liner:

``````def sbrc (n: Int) = (1 to n).find (i=> i * Integer.parseInt (i.toBinaryString.reverse, 2) == n) getOrElse (-1)
``````
-
 I can't understand the code. Can you explain the concept too? Or write it in C or JavaScript? – Mohsen Aug 15 '11 at 23:43 I put some air into the code, and tried to explain it. Hope it helps. – user unknown Aug 16 '11 at 1:04 I don't have the tool to run it but looks good. Thanks – Mohsen Aug 16 '11 at 1:07 You can evaluate it in the browser at SimplyScala.com – user unknown Aug 16 '11 at 1:12

C Sharp

``````int b(int c) { for(var i=0;i<c;i++) if(a(i)*i==c) return i; return -1;}
int a(int b) { return Convert.ToInt32(new string(Convert.ToString(b,2).Reverse().ToArray()), 2);}
``````
-
 This is incorrect. `Convert.ToInt32` will use two's complement. You want to extract a number from it's mathematical binary expansion. – Thomas Eding Aug 16 '11 at 18:13

Javascript, 117 characters

``````function f(n,i){for(i=0;i<=n;++i)if(n==i*parseInt((i).toString(2).split("").reverse().join(""),2))return i;return -1}
``````
-
f should accept one parameter – Mohsen Aug 16 '11 at 1:00
if only 1 param is passed `i` starts out as `undefined` and the first for sets it to `0` before it is ever used – ratchet freak Aug 16 '11 at 14:20