23
\$\begingroup\$

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).
\$\endgroup\$
10
  • 1
    \$\begingroup\$ Is input restricted to <256? \$\endgroup\$
    – Adám
    Feb 3, 2023 at 8:17
  • \$\begingroup\$ @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.) \$\endgroup\$
    – tsh
    Feb 3, 2023 at 8:42
  • \$\begingroup\$ 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? \$\endgroup\$ Feb 3, 2023 at 8:44
  • 8
    \$\begingroup\$ The graph of this function is really intereresting Notice the regularly spaced gaps and diagonal lines \$\endgroup\$
    – mousetail
    Feb 3, 2023 at 14:39
  • 1
    \$\begingroup\$ @Shaggy No, as long as binary I/O is not the default I/O for numbers in your language. \$\endgroup\$
    – tsh
    Feb 4, 2023 at 1:00

36 Answers 36

12
\$\begingroup\$

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=1 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.
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 4, 2023 at 19:03
7
\$\begingroup\$

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 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)
\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – mousetail
    Feb 3, 2023 at 9:00
  • 1
    \$\begingroup\$ 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)? \$\endgroup\$ Feb 3, 2023 at 9:20
  • 1
    \$\begingroup\$ @KevinCruijssen Fantastic! Have implemented your suggestion and saved a further 9 bytes! \$\endgroup\$ Feb 3, 2023 at 9:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Feb 3, 2023 at 9:37
  • 1
    \$\begingroup\$ @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! \$\endgroup\$ Feb 3, 2023 at 9:44
5
\$\begingroup\$

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       
\$\endgroup\$
2
  • \$\begingroup\$ How does this return the output? \$\endgroup\$
    – Seggan
    Feb 6, 2023 at 16:20
  • \$\begingroup\$ It displays ans = 27, which is the default output in Octave. \$\endgroup\$ Feb 6, 2023 at 19:51
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ range(n) should suffice, I think. \$\endgroup\$
    – Shaggy
    Feb 3, 2023 at 18:42
  • 1
    \$\begingroup\$ 61 bytes? \$\endgroup\$
    – M Virts
    Feb 4, 2023 at 4:09
  • \$\begingroup\$ @M Virts @Shaggy Thank you for your help! \$\endgroup\$
    – solid.py
    Feb 4, 2023 at 10:10
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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

Diagram

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -3 bytes by adding one column to the matrix. \$\endgroup\$
    – pajonk
    Feb 6, 2023 at 8:59
  • \$\begingroup\$ @pajonk - That's really nice! Thanks! \$\endgroup\$ Feb 6, 2023 at 12:32
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ it's 61 bytes with -lm and log2(3) \$\endgroup\$
    – c--
    Feb 4, 2023 at 17:44
  • \$\begingroup\$ @c-- Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 4, 2023 at 20:00
3
\$\begingroup\$

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!

\$\endgroup\$
3
3
\$\begingroup\$

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);
}
\$\endgroup\$
0
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Python 2.7, 73 bytes

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

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
\$\endgroup\$
2
  • \$\begingroup\$ Can you save anything by mapping over the input range instead? \$\endgroup\$
    – Shaggy
    Feb 4, 2023 at 18:52
  • 1
    \$\begingroup\$ @Shaggy thanks, I was able to save a byte by doing that! \$\endgroup\$
    – The Thonnu
    Feb 4, 2023 at 20:16
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Is log2 shorter and better at larger support(not limited by explicit 32)? \$\endgroup\$
    – l4m2
    Feb 5, 2023 at 10:16
  • \$\begingroup\$ @l4m2 Well, it would still be limited to 32-bit since we have other bitwise operations, but it's shorter indeed! \$\endgroup\$
    – Arnauld
    Feb 5, 2023 at 10:46
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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:

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

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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 18 bytes

≔⍘N²θI⍘⌊Eθ⭆θ§θ⁺κμ²

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

≔⍘N²θ

Convert the input to binary.

I⍘⌊Eθ⭆θ§θ⁺κμ²

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

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

Zsh, 70 bytes

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

Try it online!

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

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.
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

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.