# Smallest Bit Rotation

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 as usual.
• This is A163381.
• The largest bit rotation is A163380. A233569 is similar but different. (The first different item is the 37th).
• Is input restricted to <256?
Feb 3 at 8:17
• @Adám No, it doesn't have a boundary. You program may fail / time out if the input is too large, as long as the algorithm used could in theory work for any large numbers. (For example, hard code searching domain as 1..256 is not valid. But a program search from 1 to 2^n is valid.)
– tsh
Feb 3 at 8:42
• To follow up on Adám's question: Is it enough that the algortihm works for large numbers, even if the data type is 8-bit integers by default? Feb 3 at 8:44
• The graph of this function is really intereresting Notice the regularly spaced gaps and diagonal lines Feb 3 at 14:39
• @Shaggy No, as long as binary I/O is not the default I/O for numbers in your language.
– tsh
Feb 4 at 1:00

# x86-64 machine code, 18 bytes

0F BD D7 89 F8 0F B3 D7 D1 D7 39 C7 0F 42 C7 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.
mov eax, edi    # Set EAX to n. EAX will hold the lowest rotation found so far.
r:  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 edi, eax    # Compare EDI and EAX.
cmovb eax, edi  # If EDI was lower than EAX, set EAX to EDI.
jne r           # Jump back if they were not equal.
#  (Once a value repeats, all possible values have been seen.)
ret             # Return.

• Fun fact: on modern Intel CPUs, adc edi,edi (1 uop) is faster than rcl edi,1 (3 uops because it writes only some but not all FLAGS from the SPAZO group). uops.info. But they're the same length so no benefit in terms of code golf. Clever use of BSR and BTR+RCL to do a variable-width rotate, and termination condition instead of a counted loop. Feb 4 at 19:03

# 05AB1E, 6 bytes

bā._Cß


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

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)


# Excel, 818071 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!

• All of them, in utf-8 any Unicode value over 128 will be encoded as 2 or more bytes, this includes the Greek letters you are using. Feb 3 at 9:00
• I've never really programmed in Excel, so not sure if what I'm saying is correct (my local Excel is Dutch, so can't easily verify it right now). But can RIGHT(a,b-c)&LEFT(a,c) perhaps be golfed to MID(a&a,c,b)? Feb 3 at 9:20
• @KevinCruijssen Fantastic! Have implemented your suggestion and saved a further 9 bytes! Feb 3 at 9:31
• Also, are those ,, necessary for the SEQUENCE? Since you're using the defaults, I think just SEQUENCE(b) would do? PS: I tried porting your formula to my Dutch Excel just yet out of curiosity and for fun, and it's =LET(a;DEC.N.BIN(A1);b;LENGTE(a);c;REEKS(b);MIN(BIN.N.DEC(DEEL(a&a;c;b)))) (74 bytes), haha. I still think it's stupid Excel translates the formulas tbch, although I guess I can kinda understand it for the people who don't know any English. Feb 3 at 9:37
• @KevinCruijssen Actually, I'm not using the default for SEQUENCE's third parameter, which is 1; omitting it is equivalent to setting it to zero, which I thought I required. Now I realise that I don't, however, so thanks once again! Feb 3 at 9:44

# 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

• How does this return the output? Feb 6 at 16:20
• It displays ans = 27, which is the default output in Octave. Feb 6 at 19:51

# 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


# 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!

• range(n) should suffice, I think. Feb 3 at 18:42
• 61 bytes? Feb 4 at 4:09
• @M Virts @Shaggy Thank you for your help! Feb 4 at 10:10

# 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.

# ><> (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. # 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.

• -3 bytes by adding one column to the matrix. Feb 6 at 8:59
• @pajonk - That's really nice! Thanks! Feb 6 at 12:32

# JavaScript (Node.js), 63 bytes

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


Try it online!

t keeps being the needed digit

# 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

# R, 807875 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)))


Attempt This Online!

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

# 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)


# C (gcc), 73 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--!!!

• it's 61 bytes with -lm and log2(3)
– c--
Feb 4 at 17:44
• @c-- Nice one - thanks! :D Feb 4 at 20:00

# 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!

• 57 with the multi-argument form of min Feb 5 at 8:31
• @UnrelatedString ??? Did you not refresh the page for a really long time? ;-) Feb 5 at 8:50
• ...Evidently so... Feb 5 at 9:07

# C (gcc) with -lgmp, 233231 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);
}


# 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.

# 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.

# 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


# 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

# Python 2.7, 73 bytes

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


# Vyxalg, 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  • Can you save anything by mapping over the input range instead? Feb 4 at 18:52 • @Shaggy thanks, I was able to save a byte by doing that! Feb 4 at 20:16 # 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  • Is log2 shorter and better at larger support(not limited by explicit 32)? – l4m2 Feb 5 at 10:16 • @l4m2 Well, it would still be limited to 32-bit since we have other bitwise operations, but it's shorter indeed! Feb 5 at 10:46 # 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  # 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 • 78 bytes Feb 18 at 21:18 # 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  # 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. # Zsh, 70 bytes b=$[[##2]$1];for i ({1..$#b})m+=($[2#${b:$i}${b:0:$i}]);printf${(n)m}


Try it online!

# Husk, 7 bytes

ḋ▼U¡ṙ1ḋ


Try it online!

      ḋ  # convert to bits,
¡     # make infinite list by repeatedly
ṙ1   #   rotating by one position,
U      # get the longest unique prefix,
▼       # get the minimum of this,
ḋ        # and get the value from the bits.


# Desmos, 95 bytes

L=[floor(log_2N)...0]
B=mod(floor(N/2^L),2)
f(N)=[total(join(B[i+1...],B[1...i])2^L)fori=L].min


Even worse than the fish answer... at least it beats Java :P

Try It On Desmos!

Try It On Desmos! - Prettified