Smallest Bit Rotation

Question

For a given positive integer, try to find out the smallest possible rotation resulted by rotating it 0 or more bits.

For example, when the given number is 177, whose binary representation is \$10110001_{(2)}\$:

• \$ 10110001_{(2)}=177 \$
• \$ 01100011_{(2)}=99 \$
• \$ 11000110_{(2)}=198 \$
• \$ 10001101_{(2)}=141 \$
• \$ 00011011_{(2)}=27 \$
• \$ 00110110_{(2)}=54 \$
• \$ 01101100_{(2)}=108 \$
• \$ 11011000_{(2)}=216 \$

27 is the smallest rotating result. So we output 27 for 177.

Input / Output

You may choose one of the following behaviors:

• Input a positive integer \$n\$. Output its smallest bit rotation as defined above.
• Input a positive integer \$n\$. Output smallest bit rotation for numbers \$1\dots n\$.
• Input nothing, output this infinity sequence.

Due to definition of this sequence. You are not allowed to consider it as 0-indexed, and output smallest bit rotate for \$n-1\$, \$n+1\$ if you choose the first option. However, if you choose the second or the third option, you may optionally include 0 to this sequence, and smallest bit rotation for \$0\$ is defined as \$0\$. In all other cases, handling \$0\$ as an input is not a required behavior.

Test cases

So, here are smallest bit rotate for numbers \$1\dots 100\$:

 1  1  3  1  3  3  7  1  3  5
 7  3  7  7 15  1  3  5  7  5
11 11 15  3  7 11 15  7 15 15
31  1  3  5  7  9 11 13 15  5
13 21 23 11 27 23 31  3  7 11
15 13 23 27 31  7 15 23 31 15
31 31 63  1  3  5  7  9 11 13
15  9 19 21 23 19 27 29 31  5
13 21 29 21 43 43 47 11 27 43
55 23 55 47 63  3  7 11 15 19

Notes

• This is code-golf as usual.
• This is A163381.
• The largest bit rotation is A163380. A233569 is similar but different. (The first different item is the 37^th).

Answer 1

x86-64 machine code, 18 16 bytes

0F BD D7 0F 43 C7 0F B3 D7 D1 D7 39 F8 75 F4 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes \$n\$ in EDI and returns its smallest bit rotation in EAX.

In assembly:

f:  bsr edx, edi    # Set EDX to the highest position of a 1 bit in n.
r:  cmovnc eax, edi # (EAX will hold the lowest rotation found so far.)
                    #  Set EAX to EDI if CF=0. The first iteration, CF=0 always:
                    #  the value of CF after BSR is officially undefined, but it is
                    #  consistently 0 (as this code needs) on at least some CPUs.
                    #  (To not rely on this, add CLC before this for +1 byte.)
                    #  On later iterations, CF=0 if EDI ≤ EAX (from the cmp).
    btr edi, edx    # Set the bit at position EDX in EDI to 0.
                    #  Set CF to the previous value of that bit.
    rcl edi, 1      # Rotate EDI and CF together left by 1,
                    #  putting the removed bit back in at the end.
    cmp eax, edi    # Compare EAX and EDI.
    jne r           # Jump back if they are not equal.
                    #  (Once a value repeats, all possible values have been seen.)
    ret             # Return.

Answer 2

05AB1E, 6 bytes

bā._Cß

Input \$n\$; outputs the smallest bit rotation.

Try it online or verify all test cases.

Both the \$[1,n]\$ list with an input \$n\$ and infinite list would be 2 bytes longer with a leading Lε or ∞ε respectively.
Try the infinite version online.

Explanation:

b       # Convert the (implicit) input-integer to a binary-string
 ā      # Push a list in the range [1,length] (without popping the string)
  ._    # Map each integer v in the list to a v-times (left-)rotated version of the
        # binary-string
    C   # Convert each binary-string in the list back to an integer
     ß  # Pop and leave the minimum
        # (which is output implicitly as result)

Answer 3

Excel, 81 80 71 68 bytes

=LET(a,DEC2BIN(n),b,LEN(a),c,SEQUENCE(b),MIN(BIN2DEC(MID(a&a,c,b))))

Input n

With many thanks to @KevinCruijssen for the great suggestions and 11-byte improvement!

Answer 4

J, 16 bytes

[:<./2#.i.|."{#:

Try it online!

• #:: Convert \$n\$ to binary.
• i. |. " {: i. makes a list of the integers from 0 (inclusive) to \$n\$ (exclusive), then |. uses that to rotate the binary expansion of \$n\$, with its ranks being set (") to the ranks of { so that it takes each integer as a separate rotation.
• 2 #.: Convert back from binary expansions to numbers.
• [: <. /: Take the minimum, using a 'cap' to do so monadically.

Answer 5

Octave, 73 bytes

It's not pretty, and it doesn't work on TIO. But it works in the program itself.

x=de2bi(k=input(''));for i=1:k,[ans,bi2de(circshift(x',i)')];end,min(ans)

Try it online!

x=de2bi(k=input(''));for i=1:k,[ans,bi2de(circshift(x',i)')];end,min(ans)

        k=input('')                   % Take input, k = 177
x=de2bi(k=input(''));                 % Convert input to binary, k = [1 0 0 0 1 1 0 1], 
                                      % x = 177
for i=1:k,[...];end                   % Do k times (177 times)
                                      % Shortest way to make something happen enough times
               circshift(x',i)')      % Transpose x to make a vertical vector
                                      % Shift it i times, and transpose it back
                                      % Must be transposed for circshift to work
         bi2de(circshift(x',i)')      % Convert to decimal
    [ans,bi2de(...)]                  % Concatenate into a long vector 'ans'
min(ans)                              % The minimum of this vector       

Answer 6

Jelly, 5 bytes

BṙRḄṂ

Try it online!

Explanation

BṙRḄṂ  # Implicit input (n)
B      # Convert n into binary
 ṙ     # Rotate this string this many times:
  R    #  Each of the numbers in [1..n]
       # (this will generate some duplicates, but that's fine)
   Ḅ   # Convert each one back from binary
    Ṃ  # Get the minimum of this list
       # Implicit output

Answer 7

Python, 61 bytes

-5 bytes thanks to Shaggy and -5 bytes thanks to M Virts.

Takes a positive integer n as input. Outputs its smallest bit rotation in integer form.

lambda n:min(int((a:=f'{n:b}')[i:]+a[:i],2)for i in range(n))

Attempt This Online!

Answer 8

><> (Fish), 91 bytes

i0$1>:@$:@)?!v\
 ;n\^@+1$*2@ <r
$@:\?=@:$@:r-1/&~$?)@:&:
2+*2~v?:}:{%2:/.2b-%1:,
1$*2$/.38-

Try it

Instead of counting how many iterations happened, which would be expensive, this exits if the current value equals the minimum value.

Answer 9

R, 62 59 bytes

Edit: -3 bytes thanks to pajonk

\(n,j=2^(0:(i=log2(n))))min(j%*%array(n%/%j%%2,2:3+i)[-1,])

Attempt This Online!

Instead of iteratively rotating bits, we use them to fill a 2D array with one-too-many rows, with recycling, so that each column ends-up with the bits rotated (plus an extra useless row).
We can then use matrix multiplication (%*% in R) with a vector of powers-of-2 to easily calculate the values encoded by each column, and output the minimum one.

Answer 10

JavaScript (Node.js), 63 bytes

x=>'0b'+[...y=x.toString(2)].map(t=>y=y.slice(1)+t).sort()[0]-0

Try it online!

t keeps being the needed digit

Answer 11

APL (Dyalog Extended), 9 bytes

Anonymous tacit prefix function.

⌊/⍳⊥⍤⌽¨⊤¨

Try it online!

⌊/ the smallest (lit. minimum-reduction) of

⍳…¨⊤¨ for each integer in the range 1 through \$n\$, combined with the binary representation of \$n\$:

 …⍤⌽ rotate that representation that integer steps left, and then:

  ⊥ convert back to a regular number

Answer 12

R, 80 78 75 71 bytes

f=\(n,b=2^(0:log2(n)),x=n%/%b%%2)if(n)min(x%*%b,f(n-1,b,c(x[-1],x[1])))

Attempt This Online!

Recursive function that in every iteration rotates the binary representation by one place and keeps track of the minimum value.

Answer 13

Fig, \$18\log_{256}(96)\approx\$ 14.816 bytes

[KeBtLbxGWbxO'J]xq

Try it online!

Fig is missing a few important builtins, so this is longer than expected.

[KeBtLbxGWbxO'J]xq
          bx       # Get the binary form of this number
        GW         # Generate an infinite list from the binary
            O'     # Using the function...
              J]xq # Rotate by prepending the last element to the tailless list
     Lbx           # Length of the binary representation
    t              # Take that many items from the infinite list
  eB               # Convert each from binary
 K                 # Sort ascending
[                  # Take the first element (i.e. the minimum one)

Answer 14

C (gcc), ⁷³ 61 bytes

s;l;r;f(n){for(l=r=log2(s=n);r--;s=s<n?s:n)n=n%2<<l|n/2;r=s;}

Try it online!

Saved a whopping 12 bytes thanks to c--!!!

Answer 15

Python, 57 bytes

lambda n:int(min(h:=f"{n:b}",*[h:=h[1:]+k for k in h]),2)

Attempt This Online!

Old Python, 58 bytes

lambda n:int(min([h:=f"{n:b}"]+[h:=h[1:]+k for k in h]),2)

Attempt This Online!

Answer 16

C (gcc) with -lgmp, 233 231 227 bytes

• -6 thanks to ceilingcat

As it uses the GMP library, the maximum integer that this function handles is quite large. Takes a number as a string to avoid overflowing native types.

#import<gmp.h>
f(s,v,w,x,y)char*s,*v;{mpz_t c,l;mpz_init_set_str(c,s,10);mpz_init(l);for(y=x=strlen(v=mpz_get_str(0,2,c));y--;mpz_cmp(c,l)>0?mpz_set(c,l):0)w=v[x-1],bcopy(v,v+1,x-1),*v=w,mpz_set_str(l,v,2);gmp_printf("%Zd",c);}

Try it online!

Ungolfed:

#import<gmp.h>
f(s, // input value
  v, // bit representation of value
  w, // rotated bit
  x,y // bit string length and loop counter
  )char*s,*v; {
  mpz_t c,l; // current lowest value, test value
  mpz_init_set_str(c,s,10); // initialize variables
  mpz_init(l);
  for(
    y=x=strlen(v=mpz_get_str(0,2,c)); // initialize bit string
    y--;
    mpz_cmp(c,l)>0?mpz_set(c,l):0) { // adjust lowest value
    w=v[x-1]; // get rotated bit
    bcopy(v,v+1,x-1); // rotate
    *v=w; // put rotated bit at top
    mpz_set_str(l,v,2); // get test value
  }
  gmp_printf("%Zd",c);
}

Answer 17

Desmos, 62 bytes

L=floor(log_2n)
i=2^{[0...L]}
f(n)=min((n+mod(n,i)(2^L2-1))/i)

Try it on Desmos!

Try it on Desmos (prettified)!

-4 thanks to Aiden Chow (removing backslashes)

This uses some ideas from DesmosEnthusiast's answer (along with stealing its test harness) - go upvote that!

The way this works is that, if we want to shift a L-bit number n left by x bits:

  L=8
/------\
11011001

We can multiply the last x bits of the number, i.e. n mod 2^x, by 2^L-1, and add it to the original:

     11011001
+ 001
-         001
= 00111011

And then divide by 2^x to get the shifted number, in this case 00111011.

The expression (n+\mod(n,i)(2^L2-1))/i does this - i is a power of 2, and this shifts up the trailing digits then shifts down the whole number. But, instead of applying this to one power of two at a time, we let i be a vector of all the powers of 2 up to n (i=2^{[0...L]}), and this gives an array of all possible rotations which we can then take the minimum of.

Answer 18

Python 2, 76 bytes

i,o=bin(input())[2:],[]
for x in i:i=i[-1]+i[:-1];o+=[int(i,2)]
print min(o)

Try it online!

Python2 because it accepts integers directly as input (no int() required) and it saves a space on the print statement by not needing brackets.

Answer 19

Retina 0.8.2, 55 bytes

.+
$*
+r`\1(1+)
0$1
10
1
.
$&$'$`¶
1
10
+`01
110
O`
\G1

Try it online! Explanation:

.+
$*

Convert to unary.

+r`\1(1+)
0$1
10
1

Convert to mirrored binary i.e. LSB first, MSB last.

.
$&$'$`¶

Generate all of the rotations.

1
10
+`01
110

Convert each rotation back to unary.

O`

Sort.

\G1

Convert the shortest to decimal.

Answer 20

Factor, 43 bytes

[ >bin all-rotations [ bin> ] map infimum ]

Try it online!

>bin              ! convert input from decimal to a binary string
all-rotations     ! get every rotation as a sequence of strings
[ bin> ] map      ! convert each to decimal from binary
infimum           ! get the smallest one

Answer 21

K (ngn/k), 16 bytes

&/2/'{1_x,*x}\2\

Try it online!

• 2\ convert (implicit) input to its binary representation
• {1_x,*x}\ build a list of all rotations of the bits
• 2/' convert each back to its decimal representation
• &/ calculate, and (implicitly) return the minimum

Answer 22

Python 2.7, 73 bytes

x=bin(input())[2:]
print min([int(x[i:]+x[:i],2)for i in range(len(x))])

Answer 23

Vyxal g, 7 6 bytes

ƛ?b$ǓB

Try it online!

• -1 thanks to a suggestion from Shaggy

Explanation

ƛ?b$ǓB  # Implicit input
ƛ       # Map over the range:
 ?b     #  Get the input in binary
   $Ǔ   #  Rotate ^ ^^ times
     B  #  Convert it back from binary
        # g flag gets the minimum of this list
        # Implicit output

Previous 7-byter:

b:ż¨VǓB  # Implicit input
b        # Convert the input to binary
 :ż      # Duplicate and push range(len(^))
   ¨V    # Map over each element in ^:
     Ǔ   #  Rotate ^^^ ^ places to the left
      B  # Convert each back from binary
         # g flag gets the minimum of this list
         # Implicit output

Answer 24

JavaScript (ES6), 57 bytes

-2 bytes thanks to @l4m2

n=>(m=g=q=>x--?g(q%2<<Math.log2(n,m=m<q?m:q)|q/2):m)(x=n)

Try it online!

Commented

n => (              // n = input
  m =               // m = minimum value, initially non-numeric
  g =               // g is a recursive function taking
  q =>              // the current rotation q
  x-- ?             // if x is not equal to 0 (decrement it afterwards):
    g(              //   do a recursive call:
      q % 2 <<      //     using the number of bits in the original
      Math.log2(    //     input, left-shift the LSB so that it takes
        n,          //     the place of the MSB
        m = m < q ? //     update m to min(m, q)
          m         //     (this always updates m to q if m is
        :           //     still non-numeric)
          q         //
      ) | q / 2     //     right-shift all other bits by 1 position
    )               //   end of recursive call
  :                 // else:
    m               //   stop and return m
)(x = n)            // initial call to g with q = x = n

Answer 25

MATL, 13 12 bytes

:"GB@YSXBvX<

1 byte saved thanks to @lmendo

Try it at MATL Online!

Explanation

       % Implicitly grab the input (N)
:      % Create an array from [1...N]
"      % For each value in the array
  G    % Grab the input as a number
  B    % Convert to an array of booleans representing the binary equivalent
  @YS  % Circularly shift by the loop index
  XB   % Convert the result from binary to decimal
  v    % Vertically concatenate the entire stack
  X<   % Compute the minimum value so far
       % Implicitly display the result

Answer 26

Julia 1.0, 84 78 bytes

!x=(c=string(x,base=2);r=keys(c);min((r.|>i->parse(Int,"0b"*(c^2)[i.+r]))...))

Try it online!

• c is the bitstring of input x. Another method would be lstrip(bitstring(x),'0').
• r contains the indices in c and is iterated over the repeated bitstring c^2 to get each rotation.
• min treats a vector V as a single value, so the splat operator is used: min(V...). Another method would be minimum(V).

-6 bytes thanks to MarcMush:

• Replace range 1:length(c) with iterator keys(c)
• Use broadcasting

Answer 27

Desmos, 98 bytes

f(n)=r(n,n,0,\floor(\log_2n))
r(u,a,i,L)=\{i=L:a,r(t,\min(t,a),i+1,L)\}
t=m2^L+(u-m)/2
m=\mod(u,2)

This program works by simplifying bit rotations to the following logic:

    If the least significant bit is 0:
        Divide by 2

    If the least significant bit is 1:
        Subtract 1
        Divide by 2
        Add most significant bit

For the 177 case, to rotate it to the right, we look at the least significant bit by applying mod(177,2). The resulting 1 tells us the rotated number is (177 - 1) / 2 + 128 = 216. This method is recursively called, and the minimum is passed back. The power of this method is there is no converting to and from binary, and the recursion avoids the need to support list comprehension.

Try in on Desmos!

Try in on Desmos! - prettified

Answer 28

Java 10, 118 bytes

n->{var b=n.toString(n,2);for(int l=b.length(),i=l,t;i-->0;n=t<n?t:n)t=n.parseInt((b+b).substring(i,i+l),2);return n;}

Input \$n\$; outputs the smallest bit rotation.

Try it online.

Explanation:

n->{                       // Method with Integer as both parameter and return-type
  var b=n.toString(n,2);   //  Convert the input-integer to a binary-String
  for(int l=b.length(),    //  Set `l` to the length of this binary-String
      i=l,t;i-->0          //  Loop `i` in the range (l,0]:
      ;                    //    After every iteration:
       n=t<n?              //     If `t` is smaller than `n`:
             t:n)          //      Set `n` to this new minimum `t`
    t=                     //   Set `t` to:
      n.parseInt(          //    The following binary converted to a base-10 integer:
         (b+b)             //     Append the binary-String to itself
         .substring(i,i+l) //     And then get its substring in the range [i,i+l)
       ,2);
  return n;}               //  Return the modified `n` holding the smallest result

Answer 29

Charcoal, 18 bytes

≔⍘Ｎ²θＩ⍘⌊Ｅθ⭆θ§θ⁺κμ²

Try it online! Link is to verbose version of code. Explanation:

≔⍘Ｎ²θ

Convert the input to binary.

Ｉ⍘⌊Ｅθ⭆θ§θ⁺κμ²

Generate all of the rotations, take the minimum, and convert back to decimal.

Answer 30

Zsh, 70 bytes

b=$[[##2]$1];for i ({1..$#b})m+=($[2#${b:$i}${b:0:$i}]);printf ${(n)m}

Try it online!