22
\$\begingroup\$

Background

The Hamming weight of an integer is the number of ones in its binary representation. For this challenge, integers are represented with 32 bits, and they are unsigned.

Challenge

Given an integer between 0 and 2^32-1 (non-inclusive), output a different integer within the same range, and also with the same Hamming weight.

Examples

Input (Decimal) | Input (Binary) | Hamming weight | Possible output (Decimal)
       46       |   0b0010 1110  |       4        |      15
       12       |   0b0000 1100  |       2        |      3
        1       |   0b0000 0001  |       1        |      2
        3       |   0b0000 0011  |       2        |      6
      2^31      |   0b1000....0  |       1        |      1
      2^31+2    |   0b1000...10  |       2        |      3
      2^32-5    |   0b1111..011  |       31       |      2^31-1
      2^32-2    |   0b1111....0  |       31       |      2^31-1
        0       |   0b0000 0000  |       0        | None (This case need not be handled)
      2^32-1    |   0b1111....1  |       32       | None (This case need not be handled)

Scoring

This is , so the solution in the fewest bytes in each language wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'd suggest adding an odd number between 2^31+1 and 2^32-3, as some answers are failing at that. \$\endgroup\$ – Ørjan Johansen Jun 2 '17 at 8:06
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Jun 2 '17 at 8:49
  • \$\begingroup\$ Since you just added 2^31+2, I'll repeat that I said an odd number. The answers in question only failed when both the highest and the lowest bit are 1. \$\endgroup\$ – Ørjan Johansen Jun 3 '17 at 4:16
  • \$\begingroup\$ I'm a fool. Thank you. Will fix that \$\endgroup\$ – musicman523 Jun 3 '17 at 12:10
  • 1
    \$\begingroup\$ @musicman523 I just happened to be browsing active questions and saw this one. And noticed that you still haven't added the requested test cases. \$\endgroup\$ – Draco18s Apr 29 at 13:47

19 Answers 19

29
\$\begingroup\$

x86-64 assembly, 5 4 bytes

   0:   97                      xchg   %eax,%edi
   1:   d1 c0                   rol    %eax
   3:   c3                      retq   

A function using the C calling convention that bitwise rotates its argument left by 1 bit.

\$\endgroup\$
  • \$\begingroup\$ Dammit - I was about to post exactly this - well done :) \$\endgroup\$ – Digital Trauma Jun 1 '17 at 23:06
  • 12
    \$\begingroup\$ assembly beats Jelly :o \$\endgroup\$ – Uriel Jun 1 '17 at 23:44
  • \$\begingroup\$ Isn't this multiplying by 2? If so, then my 2 byte Pyth answer probably wins \$\endgroup\$ – NoOneIsHere Jun 2 '17 at 17:08
  • \$\begingroup\$ @NoOneIsHere No, this is not multiplication by 2. Multiplication by 2 sends half of the inputs outside of the required range, and if you ignore the overflow bit on the left, you’ve decreased the Hamming weight by 1. This is a bitwise rotation, which brings the overflow bit back in from the right. \$\endgroup\$ – Anders Kaseorg Jun 2 '17 at 17:51
  • 1
    \$\begingroup\$ @DigitalTrauma GCC 4.9.0 and later are smart enough to compile n << 1 | n >> 31 into rol instead of ror (saving a byte). \$\endgroup\$ – Anders Kaseorg Jun 3 '17 at 7:08
8
\$\begingroup\$

Python, 20 bytes

lambda x:x*2%~-2**32

Bitwise rotation left by 1 bit.

\$\endgroup\$
6
\$\begingroup\$

MATL, 9 bytes

32&B1YSXB

Circularly shifts the 32-digit binary representation one step to the right.

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Jelly, 10 8 bytes

‘&~^^N&$

Swaps the least significant set and unset bit.

Try it online!

How it works

‘&~^^N&$  Main link. Argument: n

‘         Increment; yield n+1, toggling all trailing set bits and the rightmost
          unset bit.
  ~       Bitwise NOT; yield ~n, toggling ALL bits of n.
 &        Bitwise AND; yield (n+1)&~n, keeping the only bit that differs in n+1 and
          ~n, i.e., the rightmost unset bit.
   ^      Perform bitwise XOR with n, toggling the rightmost unset bit.
       $  Combine the two links to the left into a monadic chain.
     N        Negate; yield -n. Since ~n = -(n+1) in 2's complement, -n = ~n+1.
      &       Take the bitwise AND of n and -n. Since -n = ~n + 1 and n = ~~n, the
              same reasoning that applied for (n+1)&~n applies to -n&n; it yields
              the rightmost unset bit of ~n, i.e., the rightmost set bit of n.
    ^      XOR the result to the left with the result to the right, toggling the
           rightmost set bit of the left one.
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 35 31 bytes

Looks for the first bit transition (0 → 1 or 1 → 0) and inverts it.

f=(n,k=3)=>(n&k)%k?n^k:f(n,k*2)

Demo

f=(n,k=3)=>(n&k)%k?n^k:f(n,k*2)

;[ 46, 12, 255, 2**32-2 ]
.map(n => {
  r = f(n);
  console.log((n >>> 0), '=', (n >>> 0).toString(2), '-->', (r >>> 0), '=', (r >>> 0).toString(2));
})

Bit rotation, 14 bytes

Much shorter but less fun.

n=>n>>>31|n<<1

Demo

let f =

n=>n>>>31|n<<1

;[ 46, 12, 255, 2**32-2 ]
.map(n => {
  r = f(n);
  console.log((n >>> 0), '=', (n >>> 0).toString(2), '-->', (r >>> 0), '=', (r >>> 0).toString(2));
})

\$\endgroup\$
  • \$\begingroup\$ The JavaScript bitwise operators give 32-bit signed integers rather than unsigned. For example, f(2147483647) is -1073741825 and (n=>n>>>31|n<<1)(2147483647) is -2. \$\endgroup\$ – Anders Kaseorg Jun 1 '17 at 23:11
  • 2
    \$\begingroup\$ It's fine as long as there are no more than 32 bits. \$\endgroup\$ – musicman523 Jun 1 '17 at 23:51
  • \$\begingroup\$ Can you add an explanation for the first one? I'm trying to learn Javascript, and am kind of at a loss as to how you are calling f with k undefined and still getting a reasonable answer! \$\endgroup\$ – musicman523 Jun 1 '17 at 23:59
  • 2
    \$\begingroup\$ @musicman523 Here is the corresponding tip. Basically, k is initially set to undefined and we take advantage of the fact that ~undefined equals -1. \$\endgroup\$ – Arnauld Jun 2 '17 at 0:03
  • \$\begingroup\$ @musicman523 (I'm not using this tip anymore in the updated version. But don't hesitate to ask if you have other questions about the original answer.) \$\endgroup\$ – Arnauld Jun 2 '17 at 0:27
4
\$\begingroup\$

Brain-Flak, 78 bytes

(([()()])[[]()]){((){}<({({})({}())}{})>)}{}([(({}(({}){})())<>)]){({}())<>}{}

Try it online!

Returns 2n if n < 2^31, and 2n+1-2^32 otherwise. Unfortunately, because Brain-Flak doesn't have any fast way to determine the sign of a number, the program times out on TIO if the input differs from 2^31 by more than about 500000.

Explanation

First, push -2^32 onto the stack:

(([()()])[[]()])                               push (initial value) -2 and (iterator) -5
                {((){}<                >)}     do 5 times:
                       ({({})({}())}{})        replace the current (negative) value with the negation of its square
                                            {}   pop the (now zero) iterator

Then, compute the desired output:

      (({}){})                        replace n by 2n on left stack
   ({}        ())                     push 2n+1-2^32 on left stack
  (              <>)                  push again on right stack
([                  ])                push its negation on right stack
                      {({}())<>}      add 1 to the top value of each stack until one of them reaches zero
                                {}    pop this zero, and implicitly print the number below it on the stack
\$\endgroup\$
3
\$\begingroup\$

dc, 10

?2~z31^*+p

Try it online.

This is an arithmetic implementation of a 32bit right-rotate:

?           # input
 2~         # divmod by 2 - quotient pushed first, then the remainder
   z        # z pushes the size of the stack which will be 2 (quotient and remainder) ...
    31^     #  ... and take that 2 to the 31st power
       *    # multiply the remainder by 2^31
        +   # add
         p  # output
\$\endgroup\$
3
\$\begingroup\$

Java 8, 117 17 29 bytes

n->n*2%~-(long)Math.pow(2,32)

+12 bytes by changing int to long, because int's max size is 2³¹-1

100 89 bytes saved by creating a port of @AndersKaseorg's amazing Python answer.

Try it here.

Outputs:

46 (101110):                                     92 (1011100)
12 (1100):                                       24 (11000)
1 (1):                                           2 (10)
3 (11):                                          6 (110)
10000 (10011100010000):                          20000 (100111000100000)
987654 (11110001001000000110):                   1975308 (111100010010000001100)
2147483648 (10000000000000000000000000000000):   1 (1)
4294967294 (11111111111111111111111111111110):   4294967293 (11111111111111111111111111111101)

Old answer (117 118 bytes):

n->{long r=0;for(;!n.toBinaryString(++r).replace("0","").equals(n.toBinaryString(n).replace("0",""))|r==n;);return r;}

+1 byte by changing int to long, because int's max size is 2³¹-1

Try it here.

Outputs:

46 (101110):                                     15 (1111)
12 (1100):                                       3 (11)
1 (1):                                           2 (10)
3 (11):                                          5 (101)
10000 (10011100010000):                          31 (11111)
987654 (11110001001000000110):                   255 (11111111)
2147483648 (10000000000000000000000000000000):   1 (1)
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 29 bytes

Mod@##+Quotient@##&[2#,2^32]&

Try it at the Wolfram sandbox

Rotates left arithmetically: first multiply by 2, which possibly shifts the number out of range, then cut off the out-of-range digit with Mod[...,2^32] and add it back on the right with +Quotient[...,2^32].

(Mathematica does have a single builtin that gives the modulus and the quotient in one go, but it's QuotientRemainder, which is a bit of a golfing handicap…)

\$\endgroup\$
  • \$\begingroup\$ Mod 2^32-1? (4 more to go) \$\endgroup\$ – user202729 Jun 2 '17 at 4:00
2
\$\begingroup\$

APL, 12 bytes

(2⊥32⍴1)|2×⊢

How?

           ⊢  ⍝ monadic argument
         2×   ⍝ shift left (×2)
(2⊥32⍴1)|     ⍝ modulo 2^32 - 1
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 5 bytes

·žJ<%

Try it online!

Explanation

Uses the trick to rotate the binary representation left by 1 bit from Anders Kaseorg's python answer.

·       # input * 2
    %   # modulus
 žJ<    # 2^32-1
\$\endgroup\$
1
\$\begingroup\$

R, 42 63 bytes

function(x){s=x;while(s==x){sample(binaryLogic::as.binary(x))}}

Shuffles the bits around randomly, but checks to make sure it didn't return the same number by chance.

\$\endgroup\$
1
\$\begingroup\$

Whitespace, 81 80 bytes

(1 byte saved thanks to @Ørjan Johansen reminding me dup is shorter than push 0)

   
 
 	
					 
    	 
	 		
	 
   	        
 
 	  
 
 	  
	   
  
   	 
	 	 	
 	

Try it online!

Basically implements a cyclic right bitshift using integer arithmetic. Pushing a large constant is expensive in Whitespace so we save some bytes by pushing 2^8 and squaring it twice. (Saves 1 byte over (2^16)^2 and 10 bytes over pushing 2^32 directly.)

Explanation

sssn  ; push 0
sns   ; dup
tntt  ; getnum from stdio
ttt   ; retrieve n from heap and put it on the stack
sns   ; dup
ssstsn ; push 2
tstt  ; mod - check if divisible by 2 (i.e. even)
ntsn  ; jez "even"
ssstssssssssn ; push 2^8
sns   ; dup
tssn  ; mul - square it to get 2^16
sns   ; dup
tssn  ; mul - square it to get 2^32
tsss  ; add 2^32 so MSB ends up set after the divide
nssn  ; even:
ssstsn ; push 2
tsts  ; divide by 2, aka shift right
tnst  ; putnum - display result
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can replace the second push 0 with a dup one command earlier. \$\endgroup\$ – Ørjan Johansen Jun 4 '17 at 11:17
  • \$\begingroup\$ You're right, I just finished adding shortcut syntax to my transpiler so I've been using it too much... \$\endgroup\$ – Ephphatha Jun 4 '17 at 11:18
0
\$\begingroup\$

Python 2.7, 89 bytes

Full Program:

from random import*;a=list(bin(input())[2:].zfill(32));shuffle(a);print int(''.join(a),2)

Try it online!

Suggestions welcome! :)

\$\endgroup\$
  • \$\begingroup\$ That is not valid because it can by chance return the same number again. \$\endgroup\$ – Ørjan Johansen Jun 3 '17 at 4:20
0
\$\begingroup\$

Pari/GP, 15 bytes

n->2*n%(2^32-1)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 5 bytes

Ñ%3pH

Bitwise rotation, like most answers here.

Try it

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 39 bytes

$_=sprintf'0b%b',$_;$_=oct$_.int s/10//

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 45 bytes

lambda i:int(f'{i:32b}'[1:]+f'{i:32b}'[:1],2)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C++ (gcc), 45 39 bytes

-6 bytes thanx to ceilingcat

auto h(unsigned x){return x%2<<31|x/2;}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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