It's well known in mathematics that integers can be put into a one-to-one correspondence with pairs of integers. There are many possible ways of doing this, and in this challenge, you'll implement one of them and its inverse operation.

The task

Your input is a positive integer n > 0. It is known that there exist unique non-negative integers a, b ≥ 0 such that n == 2a * (2*b + 1). Your output is the "flipped version" of n, the positive integer 2b * (2*a + 1).

You can assume that the input and output fit into the standard unsigned integer datatype of your language.

Rules and scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

These are given in the format in <-> out, since the function to be implemented is its own inverse: if you feed the output back to it, you should get the original input.

1 <-> 1
2 <-> 3
4 <-> 5
6 <-> 6
7 <-> 8
9 <-> 16
10 <-> 12
11 <-> 32
13 <-> 64
14 <-> 24
15 <-> 128
17 <-> 256
18 <-> 48
19 <-> 512
20 <-> 20
28 <-> 40
30 <-> 384
56 <-> 56
88 <-> 224
89 <-> 17592186044416


Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language. To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=70299,OVERRIDE_USER=32014;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

  • 1
    \$\begingroup\$ Funny, this problem was posted on anarchy golf last week \$\endgroup\$
    – feersum
    Jan 27, 2016 at 16:51
  • \$\begingroup\$ @feersum Oh, I wasn't aware. What a coincidence. \$\endgroup\$
    – Zgarb
    Jan 27, 2016 at 16:53
  • 2
    \$\begingroup\$ Obligatory xkcd.com/153 \$\endgroup\$
    – corsiKa
    Jan 27, 2016 at 22:56

14 Answers 14


Jelly, 17 16 15 bytes


Try it online!

How it works

BUi1µ2*³:2*×Ḥ’$    Main link. Input: n

B                  Convert n to base 2.
 U                 Reverse the array of binary digits.
  i1               Get the first index (1-based) of 1.
                   This yields a + 1.
    µ              Begin a new, monadic chain. Argument: a + 1
     2*            Compute 2 ** (a+1).
       ³:          Divide n (input) by 2 ** (a+1).
                   : performs integer division, so this yields b.
         2*        Compute 2 ** b.
              $    Combine the two preceding atoms.
            Ḥ      Double; yield 2a + 2.
             ’     Decrement to yield 2a + 1.
           ×       Fork; multiply the results to the left and to the right.
  • \$\begingroup\$ Wait, are you implementing operators in Jelly to suit the problem? In that case LOL \$\endgroup\$ Jan 28, 2016 at 13:00
  • \$\begingroup\$ I am not. The only commit to Jelly after this challenge was posted was an update of the documentation, and all the operator used in this answer have been implemented for at least a month. Feel free to verify \$\endgroup\$
    – Dennis
    Jan 28, 2016 at 14:45
  • \$\begingroup\$ No worries, I'm not familiar with the rules or anything, I just thought it was cool that golfing has come to people inventing their own languages! \$\endgroup\$ Jan 28, 2016 at 14:57
  • 2
    \$\begingroup\$ And there's a lot of them. Check out What programming languages have been created by PPCG users?. \$\endgroup\$
    – Dennis
    Jan 28, 2016 at 15:01

Pyth, 16 15 bytes


1 byte thanks to Dennis

Test suite


                    Implicit: Q = eval(input())
     PQ             Take the prime factorization of Q.
    /  2            Count how many 2s appear. This is a.
   J                Save it to J.
  y                 Double.
 h                  +1.
          .>QhJ     Shift Q right by J + 1, giving b.
        ^2          Compute 2 ** b.
*                   Multiply the above together, and print implicitly.

MATL, 22 bytes


Try it online!


Yf      % factor
t       % duplicate
2=      % compare to 2 (yields a logical array)
XK      % save a copy of that to variable K
~)      % keep only values != 2 in the factors array
p       % multiply that factors
q2/     % product - 1 / 2
2w^     % 2^x

K       % load variable K (the logical array)
s       % sum (yields the number of 2s)
2*Q     % count * 2 + 1

*       % multiply both values
  • \$\begingroup\$ Very nice! You can use Q for 1+ (this has been introduced recently) and q for 1-. That also saves a space (which you could save with H anyway). See here \$\endgroup\$
    – Luis Mendo
    Jan 27, 2016 at 17:20
  • \$\begingroup\$ @LuisMendo Thanks. Didn't know that feature. \$\endgroup\$
    – Rainer P.
    Jan 27, 2016 at 17:30
  • 5
    \$\begingroup\$ Well done beating Luis using MATL! \$\endgroup\$ Jan 27, 2016 at 20:22

Python 2, 39 bytes

lambda n:2*len(bin(n&-n))-5<<n/2/(n&-n)

n & -n gives the largest power of 2 that divides n. It works because in two's-complement arithmetic, -n == ~n + 1. If n has k trailing zeros, taking its complement will cause it to have k trailing ones. Then adding 1 will change all the trailing ones to zeroes, and change the 2^k bit from 0 to 1. So -n ends with a 1 followed by k 0's (just like n), while having the opposite bit from n in all higher places.

  • \$\begingroup\$ can you shortly explain how does n&-n work ? i see what this trick do but not how :( \$\endgroup\$
    – Erwan
    Jan 27, 2016 at 22:10
  • \$\begingroup\$ n&-n returns the highest power of 2 that divdes n. \$\endgroup\$
    – Neil
    Jan 27, 2016 at 22:13
  • 1
    \$\begingroup\$ @Erwan I explained about n & -n. \$\endgroup\$
    – feersum
    Jan 27, 2016 at 22:32
  • \$\begingroup\$ I had gotten the corresponding program on Anarchy golf n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, but it's two chars behind the best solution. \$\endgroup\$
    – xnor
    Jan 27, 2016 at 22:33
  • \$\begingroup\$ @xnor Hint: the 59-byte solution (well, mine at least) does not work for all values of n. \$\endgroup\$
    – feersum
    Jan 27, 2016 at 22:35

MATL, 25 26 bytes


This uses current release (10.2.1) of the language/compiler.

Try it online!


Pretty straightforward, based on brute force. Tries all combinations of a and b, selects the appropriate one and does the required computation.

:q          % implicit input "n". Generate row vector [0,1,...,n-1], say "x"
t2w^        % duplicate and compute 2^x element-wise
w!2*Q       % swap, transpose to column vector, compute 2*x+1
*           % compute all combinations of products. Gives 2D array
G=2#f       % find indices where that array equals n
2*q2bq^*    % apply operation to flipped values
  • 1
    \$\begingroup\$ Hah! :-P Beaten in your own language... first time? \$\endgroup\$ Jan 27, 2016 at 20:22
  • \$\begingroup\$ @StewieGriffin Yep! A nice milestone :-) \$\endgroup\$
    – Luis Mendo
    Jan 28, 2016 at 0:48

Julia, 41 bytes


This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

We define a as 1 + the exponent of 2 in the prime factorization of n. Since factor returns a Dict, we can use get with a default value of 0 in case the prime factorization doesn't contain 2. We right bit shift n by a, and take 2 to this power. We multiply that by 2a-1 to get the result.


Perl 5, 40 bytes

38 bytes plus 2 for -p


-p reads the STDIN into the variable $_.

$i++,$_/=2until$_%2 increments $i (which starts at 0) and halves $_ until $_ is nonzero mod 2. After that, $_ is the odd factor of the original number, and $i is the exponent of 2.

$_=2*$i+1<<$_/2-.5 — The right-hand side of the = is just the formula for the number sought: {1 more than twice the exponent of 2} times {2 to the power of {half the odd factor minus a half}}. But "times {2 to the power of…}" is golfed as "bit-shifted leftward by…". And that right-hand side is assigned to $_.

And -p prints $_.


C, 49 bytes

a;f(n){for(a=0;n%2-1;a++)n/=2;return 2*a+1<<n/2;}

JavaScript ES6, 36 33 bytes


My understanding is that Math.clz32 is going to be shorter than fiddling around with toString(2).length.

Edit: Saved 3 bytes thanks to @user81655.

  • \$\begingroup\$ Nice. You could also save a few bytes by setting n&-n to a variable: n=>63-2*Math.clz32(x=n&-n)<<n/x/2 \$\endgroup\$
    – user81655
    Jan 28, 2016 at 0:08
  • \$\begingroup\$ @user81655 Thanks; I only wish I could have used n&=-n, but I need n again... \$\endgroup\$
    – Neil
    Jan 28, 2016 at 8:54

Vyxal, 13 bytes


Try it Online!

2Ǒ            # Multiplicity by 2 = a
  :£          # Store a copy to the register
     /        # Divide the input by...
    E         # 2 ** A
      ‹½      # Decrement and halve = b
        E     # 2 ** b
            * # Multiplied by
         ¥    # a (register)
          d›  # Doubled and incremented

PARI/GP, 38 bytes


Note that >> and \ have the same precedence and are computed left-to-right, so the last part can be n>>k\2 rather than (n>>k)\2. The ungolfed version would make k lexical with my:

  (2*k+1) << ((n>>k)\2);

Pip, 24 23 18 bytes


Try It Online!

Loops, halving a and incrementing i by 2, until a halved (int division) is different from a/2 (float division), thus indicating a had become odd. The way the loop is set up, a is now half of that odd number, rounded down: i.e., if the odd factor of the original input is \$2k+1\$, a is now \$k\$. Meanwhile, if the largest power-of-two factor of the original input is \$2^n\$, then i is now \$2n\$. It remains only to increment i to \$2n+1\$ and multiply that by \$2^k\$.

The new U, E, and HV operators make a big difference for this one. Here's the original 23-byte version in Pip Classic:


Try it online!


HBL, 22 bytes


Try it here!


Here's the same thing in HBL's companion language Thimble:

'(cons (head arg1) (head arg1) arg1)

'(cond (odd? arg1)
     (pow 2 (div arg1 2))
     (recur (div arg1 2))))

'(sum (prev arg1))

The first line is a helper function that takes a list and prepends two copies of its first element to it.

The second function does most of the work. If the argument is odd (base case):

  • Int-divide it by 2
  • Raise 2 to that power
  • Return that value wrapped in a singleton list

If the argument is even (recursive case):

  • Int-divide it by 2
  • Recurse
  • Apply the helper function to the resulting list

Thus, given \$n = 2^p \cdot (2k + 1)\$, this function returns a list containing \$2p + 1\$ copies of \$2^k\$.

The third function passes its argument to the second function and then simply sums the result.


05AB1E, 14 bytes


Port of @emanresuA's Vyxal answer.

Should have been 13 bytes, but there is a bug in 05AB1E's o with certain decimal values.

Try it online or verify all test cases.


Ò            # Get all prime factors of the (implicit) input
 2¢          # Count how many 2s are in this list
   ©         # Store it in variable `®` (without popping)
    o        # Pop it, and push 2 to the power this value
     /       # Divide the (implicit) input by this value
      <      # Decrease it by 1
       ;     # Halve it
        §    # (Cast it to a string - bugfix)
         o   # Pop it, and push 2 to the power this (strinified) decimal
      ®      # Push variable `®`
       ·     # Double it
        >    # Increase it by 1
          *  # Multiply the two together
             # (which is output implicitly as result)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.