Find the Smallest Data Type for a Number

Question

Recently I had to implement this problem in c#, and thought it would make for a good code golf.

Your goal is to output the smallest unsigned data-type a 64 bit unsigned number can fit into.

Input: An unsigned 64-bit number (or the closest builtin equivalent in your chosen language)

Output: A number representing the bytes of the smallest unsigned data-type the input value can fit into (1, 2, 4, or 8)

Data Type Max Values:

byte => 255
ushort => 65535
uint => 4294967295
ulong => 18446744073709551615

Examples:

0 => 1 (byte)
255 => 1 (byte)
256 => 2 (ushort)
500 => 2 (ushort)
60000 => 2 (ushort)
4294967295 => 4 (uint)
4294967296 => 8 (ulong)
18446744073709551615 => 8 (ulong)

This can be done using lzcnt, if statements, regex, bit manipulation, etc. (creative solutions & languages encouraged!)

This is a code-golf, so shortest solution wins!

How strict is the output format? Can we output 4 other distinct values? — Arnauld, Commented Nov 27 at 15:31
@Arnauld Only output 1, 2, 4, or 8. The original problem required 1,2,4 or 8 only, so I'll stick to that. (Nice solution btw!) — Ezlanding, Commented Nov 27 at 15:41
Wait, this is not a duplicate of an age-old existing challenge? — ojdo, Commented Nov 29 at 17:31

emanresu A · Accepted Answer · 2024-11-27 20:22:27Z

6

Vyxal, 7 bytes

₈τL∆l⌈E

Try it Online!

  L     # Length
 τ      # when converting to base
₈       # 256
        # (i.e. number of bytes required) 
      E # 2 to the power of
   ∆l   # log2 of that
     ⌈  # rounded up

answered Nov 27 at 20:22

emanresu A

44.2k5 gold badges100 silver badges240 bronze badges

Add a comment |

anatolyg · Accepted Answer · 2024-11-28 15:22:22Z

x86_64 machine code, 14 bytes

B0 FF                mov         al,0FFh  
48 0F BD C0          bsr         rax,rax  
0F BD C8             bsr         ecx,eax  
B0 40                mov         al,40h  
D2 C0                rol         al,cl  
C3                   ret

If x < 2^2³, its type is 1, or 2⁰
If 2^2³ ≤ x < 2^2⁴, its type is 2, or 2¹
If 2^2⁴ ≤ x < 2^2⁵, its type is 4, or 2²
If 2^2⁵ ≤ x < 2^2⁶, its type is 8, or 2³

To apply this, we can calculate y = log2(log2(x)), and then z = 2 ** y, with suitable offsets and rounding.

To ensure good behavior near 0, the code first ensures x ≥ 255 (I think greater than 3 should be enough; used 255 for safety).

Arnauld · Accepted Answer · 2024-11-27 15:44:54Z

4

JavaScript (ES11), 29 bytes

Expects a BigInt.

f=(n,k=8n)=>n>>k?2*f(n,k+k):1

Try it online!

edited Nov 27 at 15:44

answered Nov 27 at 15:32

Arnauld

198k20 gold badges179 silver badges649 bronze badges

\$\begingroup\$ So you're checking for the exit condition floor(n / 2**x) == 0 , where x is the amount of bits you're checking for in each pass (8, 16, 32, 64), then returning 2**depth. Cool solution! \$\endgroup\$
– Ezlanding
Commented Nov 28 at 5:33

Add a comment |

Albert.Lang · Accepted Answer · 2024-11-28 11:06:00Z

4

Python, 33 bytes

f=lambda n:n<256or 8-6*f(n**.5)%8

Attempt This Online!

Returns True for 1.

How?

Same idea as @xnor's comment here. The tricky bit was fixing the fp issue cheaply.

answered Nov 28 at 11:06

Albert.Lang

4,5745 silver badges22 bronze badges

Add a comment |

colossus16 · Accepted Answer · 2024-11-28 17:13:05Z

4

Haskell, 32 29 27 bytes

f n=until(\b->n<256^b)(*2)1

Try it online!

EDIT: -3 bytes because I realized I could drop the -1 if I switched to using <

EDIT 2: -2 bytes thanks to @xnor's suggestion to use 256^b.

edited Nov 28 at 17:13

answered Nov 27 at 18:50

colossus16

2,0517 silver badges10 bronze badges

1

\$\begingroup\$ Looks like you can write n<256^b \$\endgroup\$
– xnor
Commented Nov 27 at 21:52

Add a comment |

Neil · Accepted Answer · 2024-11-27 17:12:10Z

Retina, 63 bytes

$
¶$`¶256¶65536¶4294967296
N`¶.+
Lm`^(.+)¶(.+¶)*\1$
C`¶
T`34`48

Try it online! Link includes test cases. Unfortunately I had to use Retina 1 for this as Retina 0.8.2 uses 32-bit arithmetic for sorting. Explanation:

$
¶$`¶256¶65536¶4294967296

Append a copy of the input and 256, its square and squared square.

N`¶.+

Sort the copy among the powers.

Lm`^(.+)¶(.+¶)*\1$

Find where it ended up.

C`¶

Count how many squares were needed, plus one.

T`34`48

Translate into a number of bytes.

Kevin Cruijssen · Accepted Answer · 2024-11-28 08:11:32Z

3

05AB1E, 7 bytes

₁вg.²îo

Try it online or verify all test cases.

Explanation:

₁в       # Convert the (implicit) input-integer to a base-256 list
  g      # Pop and push its length
   .²    # Take the logarithm_2 of that
     î   # Ceil it
      o  # Take 2 to the power that
         # (which is output implicitly as result)

answered Nov 28 at 8:11

Kevin Cruijssen

131k13 gold badges144 silver badges384 bronze badges

Add a comment |

Kjetil S · Accepted Answer · 2024-11-28 19:29:28Z

3

Perl 5 -p, 47 bytes

$_=$_>9e10?8:$_?1<<1+log(log()/log 256)/log 2:1

Try it online!

The 10 bytes of $_>9e10?8: could have been dropped if log had more floating point accuracy I think. And $_=$_>=1<<32?8:$_>65535?4:$_>255?2:1 is 36 bytes Try it online!

Inspired by the Python from @Lucenaposition: $_=[1,2,4,4]->[log($_|1)/log 256]||8 Try it online! 36 bytes.

edited Nov 28 at 19:29

answered Nov 27 at 18:13

Kjetil S

6,12110 silver badges22 bronze badges

Add a comment |

Neil · Accepted Answer · 2024-11-27 17:26:41Z

Charcoal, 15 bytes

ＩＸ²Ｌ↨÷⊖Ｌ⍘Ｎ²¦⁸¦²

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

         Ｎ      Input as an integer
        ⍘       Converted to string base
          ²     Literal integer `2`
       Ｌ        Length
      ⊖         Decremented
     ÷          Integer divided by
            ⁸   Literal integer `8`
    ↨           Converted to base
              ² Literal integer `2`
   Ｌ            Take the length
  ²             Literal integer `2`
 Ｘ              Raised to that power
Ｉ               Cast to string
                Implicitly print

The first base conversion converts 0 to "0" while the second one converts it to []. This makes a difference when taking the length.

Lucenaposition · Accepted Answer · 2024-11-27 22:52:33Z

2

Python 2, 37 bytes

lambda n:'12448888'[len(bin(n))-3>>3]

Try it online!

Outputs a string (if it is allowed).

Python 2, 45 bytes

lambda n:0x88884421>>((len(bin(n))-3)/8*4)&15

Try it online!

Outputs a number.

answered Nov 27 at 22:52

Lucenaposition

7811 silver badge16 bronze badges

Add a comment |

noodle person · Accepted Answer · 2024-11-28 18:12:52Z

2

Python 3.8 (pre-release), 59 47 38 34 bytes

-12 bytes by having 5 more minutes to codegolf.
-9 bytes by stealing Arnauld's idea.
-4 bytes from Arnauld.

f=lambda n,k=8:n>>k<1or 2*f(n,2*k)

Try it online!

edited Nov 28 at 18:12

noodle person

10.3k1 gold badge22 silver badges76 bronze badges

answered Nov 27 at 15:38

squareroot12621

1,1311 gold badge2 silver badges14 bronze badges

\$\begingroup\$ 37 bytes \$\endgroup\$
– Arnauld
Commented Nov 27 at 19:24
\$\begingroup\$ or 34 bytes if you don't mind returning True instead of 1 (it quacks like a 1!) \$\endgroup\$
– Arnauld
Commented Nov 27 at 19:25
\$\begingroup\$ f=lambda n:n<256or 2*f(n**.5) almost works for 29 bytes (with True==1), but float precision messes up the last test case \$\endgroup\$
– xnor
Commented Nov 27 at 21:59
\$\begingroup\$ 37 bytes: F=lambda n,b=1:n>>b*8and F(n,b+b)or b \$\endgroup\$
– tsh
Commented Nov 28 at 5:55

Add a comment |

doubleunary · Accepted Answer · 2024-11-27 16:05:07Z

1

Google Sheets, 44 bytes

=ifs(A1<2^8,1,A1<2^16,2,A1<2^32,4,A1<2^64,8)

screenshot

Google Sheets uses IEEE 754 double-precision with a significand of 53 bits for pretty much everything, so cannot go all the way up to 64-bit unsigned.

The output format rules specified in the question are quite rigid. This alternative version outputs an array where the first true value marks the minimum bytes required by the unsigned integer (23 bytes):

=sort(A2<2^2^{3,4,5,6})

screenshot2

edited Nov 27 at 16:05

answered Nov 27 at 15:15

doubleunary

2,7131 gold badge2 silver badges12 bronze badges

\$\begingroup\$ The original problem I was solving could only work with the outputs 1,2,4 or 8. And, looser output format rules was never suggested in the sandbox post. However, I am more than happy to loosen the output rules (so that any 4 distinct values could be outputted) if this inspires more creative and "golfy" answers. Do you recommend I edit the post to make this change? \$\endgroup\$
– Ezlanding
Commented Nov 27 at 16:24
1

\$\begingroup\$ Flexible I/O formats are encouraged. See Always allow flexibility, within reason, Keep your golfing in your code, not in inputs and outputs, and Default for Code Golf: Input/Output methods. But it's also good to not alter rules after answers have already been posted. In comments, Arnauld specifically asked if it's OK to output other values, and you responded "no", so perhaps it's better to stick by the original rules. \$\endgroup\$
– doubleunary
Commented Nov 27 at 17:12
\$\begingroup\$ Sounds good. I'll keep in mind the good practice of having flexible I/O for my future questions, but I'll stick with a "no" for this question :) \$\endgroup\$
– Ezlanding
Commented Nov 28 at 5:35

Add a comment |

Graham · Accepted Answer · 2024-11-27 17:46:04Z

1

APL+WIN, 26 bytes

Prompts for integer

¯1↑((2⍟1⌈⎕)≥0,2*3+⍳3)/2*⍳4

Try it online Thanks to Dyalog Classic!

answered Nov 27 at 17:46

Graham

6,8461 gold badge15 silver badges11 bronze badges

Add a comment |

pajonk · Accepted Answer · 2024-11-27 18:54:33Z

1

R, 29 27 bytes

\(n,k=2^(3:6))k[n<2^k][1]/8

Attempt This Online!

The last test-case is too large for R.

edited Nov 27 at 18:54

answered Nov 27 at 18:48

pajonk

18.3k3 gold badges25 silver badges74 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2024-11-28 09:50:00Z

MathGolf, 13 bytes

8421Γgæ♠▬k>~Þ

Try it online.

Explanation:

8421          # Push 8,4,2,1 separated to the stack
    Γ         # Wrap all four into a list: [8,4,2,1]
     g        # Filter this list by,
      æ       # using four character as inner code-block:
       ♠      #  Push 256
        ▬     #  Take 256 to the power the current value
         k    #  Push the input
          >   #  Check whether the 256 to the value is larger than the input
           ~  # After the filter: dump all remaining digits to the stack
            Þ # Only keep the last one
              # (after which the entire stack is output implicitly as result)

noodle person · Accepted Answer · 2024-11-29 00:56:25Z

1

Uiua, 11 bytes

⍜ₙ⌈2⌈ₙ256+1

Try it: Uiua pad

⌈ₙ256+1 -- The number of bits needed to represent the number is the logarithm with base 256 of 1 + the input, rounded up.

⍜ₙ⌈2 -- "under logarithm ceiling 2", so \$2^{\lceil log_2 n \rceil}\$ (where \$ \lceil x \rceil \$ means x rounded up), yielding the smallest power of 2 greater than n.

edited Nov 29 at 0:56

answered Nov 28 at 18:12

noodle person

10.3k1 gold badge22 silver badges76 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2024-11-29 18:33:59Z

0

Japt, 10 bytes

Inspired by Kevin's MathGolf solution.

@<G²pX}a!²

Try it

@<G²pX}a!²     :Implicit input of integer U
@              :Function taking an integer X as argument
 <             :  U is less than
  G            :    16
   ²           :    Squared
    pX         :    Raised to the power of X
      }        :End function
       a       :Apply the following method to the non-negative integers,
               : returning the first result that returns true
               : when passed through that function
        !²     :Power of 2

edited Nov 29 at 18:33

answered Nov 29 at 18:11

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

Stack Exchange Network

Find the Smallest Data Type for a Number

17 Answers 17

Vyxal, 7 bytes

x86_64 machine code, 14 bytes

JavaScript (ES11), 29 bytes

Python, 33 bytes

How?

Haskell, 32 29 27 bytes

Retina, 63 bytes

05AB1E, 7 bytes

Perl 5 -p, 47 bytes

Charcoal, 15 bytes

Python 2, 37 bytes

Python 2, 45 bytes

Python 3.8 (pre-release), 59 47 38 34 bytes

Google Sheets, 44 bytes

APL+WIN, 26 bytes

R, 29 27 bytes

MathGolf, 13 bytes

Uiua, 11 bytes

Japt, 10 bytes

Your Answer

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

Hot Network Questions

Find the Smallest Data Type for a Number

17 Answers 17

Vyxal, 7 bytes

x86_64 machine code, 14 bytes

JavaScript (ES11), 29 bytes

Python, 33 bytes

How?

Haskell, 32 29 27 bytes

Retina, 63 bytes

05AB1E, 7 bytes

Perl 5 -p, 47 bytes

Charcoal, 15 bytes

Python 2, 37 bytes

Python 2, 45 bytes

Python 3.8 (pre-release), 59 47 38 34 bytes

Google Sheets, 44 bytes

APL+WIN, 26 bytes

R, 29 27 bytes

MathGolf, 13 bytes

Uiua, 11 bytes

Japt, 10 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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