Am I a Cullen Number? A Cullen Number is any number that is contained in the sequence generated using the formula:

C(n) = (n*2^n)+1.  

Your Task:

Write a program or function that receives an input and outputs a truthy/falsy value based on whether the input is a Cullen Number.  

Input:

A non-negative integer between 0 and 10^9 (inclusive).  

Output:

A truthy/falsy value that indicates whether the input is a Cullen Number.    

Test Cases:

Input:    Output:
1   ---&gt;  truthy
3   ---&gt;  truthy
5   ---&gt;  falsy
9   ---&gt;  truthy
12  ---&gt;  falsy
25  ---&gt;  truthy


Scoring:

This is code-golf, so the lowest score in bytes wins.
x86_64 machine code (System V ABI), 28 27 bytes

-1 byte thanks to @Cody Gray, thanks!

A constant-time algorithm!

_cullen:
   0:   0f bd cf    bsrl    %edi, %ecx
   3:   0f bd c1    bsrl    %ecx, %eax
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx
   a:   0f bd c2    bsrl    %edx, %eax
   d:   29 c1       subl    %eax, %ecx
   f:   d3 e1       shll    %cl, %ecx
  11:   ff c1       incl    %ecx
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq


Explanation:

Let y an integer and x=y*2^y + 1.
Taking logs, we have y + log2(y) = log2(x-1), thus y=log2(x-1)-log2(y). Plugging back the value of y, we get y=log2(x-1)-log2(log2(x-1)-log2(y)). Doing this one more time, we obtain: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))]. 

Let us remove the last terms (of the order of log2(log2(log2(log2(x)))), this should be safe!), and assume that x-1≈x, we obtain:
y≈log2(x)-log2[log2(x)-log2(log2(x))]

Now, letting f(n) = floor(log2(n)), it can be verified manually that y can be exactly retrieved by:
y=f(x)-f[f(x)-f(f(x))],
for y &lt; 26, and thus x ⩽ 10^9, as specified by the challenge(1). 

The algorithm then simply consists of computing y given x, and verify that x == y*2^y + 1.
The trick is that f(n) can simply be implemented as the bsr instruction (bit-scan reverse), which returns the index of the first 1-bit in n, and y*2^y as y &lt;&lt; y.

Detailed code:

_cullen:                                 ; int cullen(int x) {
   0:   0f bd cf    bsrl    %edi, %ecx   ;  int fx = f(x);
   3:   0f bd c1    bsrl    %ecx, %eax   ;  int ffx = f(f(x));
   6:   89 ca       movl    %ecx, %edx   
   8:   29 c2       subl    %eax, %edx   ;  int a = fx - ffx;
   a:   0f bd c2    bsrl    %edx, %eax   ;  int ffxffx = f(a);
   d:   29 c1       subl    %eax, %ecx   ;  int y = fx - ffxffx;
   f:   d3 e1       shll    %cl, %ecx    ;  int x_ = y&lt;&lt;y;
  11:   ff c1       incl    %ecx         ;  x_++;
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq                 ;  return (x_ == x);
                                         ; }


(1)In fact, this equality seems to hold for values of y up to 50000.