Dla każdego dodatniej 32-bitowej liczby całkowitej ( 1 ≤ n ≤ 0xFFFFFFFF) liczba bitów potrzebnych do przedstawienia tej liczby całkowitej.

Przypadki testowe

| n    | n in binary | bits needed |
|----------------------------------|
| 1    | 1           | 1           |
| 2    | 10          | 2           |
| 3    | 11          | 2           |
| 4    | 100         | 3           |
| 7    | 111         | 3           |
| 8    | 1000        | 4           |
| 15   | 1111        | 4           |
| 16   | 10000       | 5           |
| 128  | 10000000    | 8           |
| 341  | 101010101   | 9           |

4294967295 => 11111111111111111111111111111111 => 32

Więc f(16)wydrukuje lub wróci5

To jest golf golfowy . Najkrótszy kod w bajtach wygrywa

05AB1E , 2 bajty

bg

Wypróbuj online!

JavaScript (ES6), 18 bajtów

f=n=>n&&1+f(n>>>1)

<input type=number min=0 step=1 value=8 oninput="O.value=f(this.value)">
<input id=O value=4 disabled>

Zestaw x86, 4 bajty

Zakładając stałą w EBX:

bsr eax,ebx
inc eax

EAX zawiera liczbę bitów niezbędną dla Constant.

Bajty: ☼¢├@

Szesnastkowy: ['0xf', '0xbd', '0xc3', '0x40']

Python , 14 bajtów

int.bit_length

Wypróbuj online!

Labirynt , 13 12 bajtów

 ?
_:
2/#(!@

Wypróbuj online!

Wyjaśnienie

Program po prostu wielokrotnie dzieli wejście przez 2, aż do zera. Liczbę kroków śledzi się, powielając wartość na każdym kroku. Po zmniejszeniu do zera drukujemy głębokość stosu (minus 1).

Program rozpoczyna się od tego, ?który odczytuje dane wejściowe. Główna pętla to blok 2x2 poniżej, idący w kierunku przeciwnym do ruchu wskazówek zegara:

:   Duplicate current value.
_2  Push 2.
/   Divide.

Gdy po pełnej iteracji wartość wynosi zero, wykonywany jest bit liniowy na końcu:

#   Push stack depth.
(   Decrement.
!   Print.
@   Terminate.

C, 31 bajtów

f(long n){return n?1+f(n/2):0;}

... Potem pomyślałem o rekurencji. Od niejasnych do oczywistych, a jedna czwarta długości spadła.

Zobacz na żywo na Coliru

C, 43 bajty

c;
#define f(v)({for(c=0;v>=1l<<c;++c);c;})

Wywołanie fz wartością bez znaku (np. f(42u)) „Zwróci” swoją długość bitu. Nawet działa dla 0u!

Nieoznakowane i wyjaśnione: (pominięto ukośniki odwrotne)

c;
#define f(v)
    ({ // GCC statement-expression

        // Increment c until (1 << c) >= v, i.e
        // that's enough bits to contain v.
        // Note the `l` to force long
        // arithmetic that won't overflow.
        for(c = 0; v >= 1l << c; ++c)
            ; // Empty for body

        c; // Return value
    })

Zobacz na żywo na Coliru

Mathematica, 9 bajtów

BitLength

Alternatywnie:

Floor@Log2@#+1&
#~IntegerLength~2&

Perl 6 , 7 bajtów

*.msb+1

Spróbuj

Wyjaśnienie:

* sprawia, że ​​staje się on lambda WhokolwiekCode i wskazuje, gdzie umieścić dane wejściowe

.msb na Int zwraca indeks najbardziej znaczącego bitu (w oparciu o 0)

+1jest łączony w lambda i dodaje jeden do ostatecznego wyniku wywołania .msb.

Makro preprocesora C (z rozszerzeniami gcc), 26

#define f 32-__builtin_clz

Wykorzystuje wbudowane liczniki wiodące zer GCC .

Nazwij to jako funkcję, np f(100).

Wypróbuj online .

Siatkówka , 56 37 bajtów

To rozwiązanie działa ze wszystkimi wymaganymi wartościami wejściowymi.

Największym problemem, z którym mierzy się Retina w tym wyzwaniu, jest to, że jego łańcuchy mają maksymalną długość 2 ^ 30 znaków, więc zwykły sposób radzenia sobie z liczbami (reprezentacja jedności) nie działa z wartościami większymi niż 2 ^ 30.

Aby rozwiązać ten problem, podjąłem inne podejście, zachowując rodzaj dziesiętnej reprezentacji liczb, ale gdzie każda cyfra jest zapisywana w jedności (nazywam tę reprezentację cyfrową ). Na przykład numer 341byłby zapisany jak 111#1111#1#w cyfrowej. Dzięki tej reprezentacji możemy teraz pracować z liczbami do 2^30/10cyfr (~ sto milionów cyfr). Jest mniej praktyczny niż standardowe jednoargumentowe dla dowolnej arytmetyki, ale przy odrobinie wysiłku możemy wykonać dowolne operacje.

UWAGA: cyfrowo w teorii można użyć dowolnej innej podstawy (np. Binarne 110byłoby 1#1##w bazie 2 cyfrowo), ale ponieważ Retina ma wbudowane funkcje do konwersji między dziesiętną i jednostkową i nie ma bezpośredniego sposobu radzenia sobie z innymi bazami, liczba dziesiętna jest prawdopodobnie najłatwiejszą do zarządzania bazą.

Algorytm, którego użyłem, dokonuje kolejnych podziałów całkowitych o dwa, aż osiągniemy zero, liczba dokonanych podziałów to liczba bitów potrzebna do przedstawienia tej liczby.

Jak dzielimy przez dwa cyfrowo? Oto fragment kodu Retina:

(1*)(1?)\1#        We divide one digit, the first group captures the result, the second group captures the remainder
$1#$2$2$2$2$2      The result is put in place of the old number, the remainder passes to the next digit (so it is multiplied by 10) and is divided by two there -> 5 times the remainder goes to the next digit

Ta zamiana wystarczy, aby podzielić cyfrę cyfrową przez 2, wystarczy usunąć ewentualne 0,5 s od końca, jeśli oryginalny numer był nieparzysty.

Oto pełny kod, dzielimy przez dwa, dopóki cyfry nie będą zawierać cyfr, i umieszczamy literę nprzed ciągiem przy każdej iteracji: liczba nna końcu jest wynikiem.

.                  |
$*1#               Convert to digitunary
{`^(.*1)           Loop:|
n$1                    add an 'n'
(1*)(1?)\1#            |
$1#$2$2$2$2$2          divide by 2
)`#1*$                 |
#                      erase leftovers
n                  Return the number of 'n's in the string

Wypróbuj online!

Wielkie refaktoryzacja z wieloma dobrymi pomysłami, które grały w golfa na około jednej trzeciej długości, wszystko dzięki Martinowi Enderowi!

Główną ideą jest użycie _jako naszego jednoznacznego symbolu: w ten sposób możemy używać regularnych cyfr w naszym ciągu, o ile przekonwertujemy je z powrotem na_ s, gdy jest to potrzebne: pozwala nam to zaoszczędzić wiele bajtów na dzieleniu i wstawianiu wielu cyfry

Oto kod:

<empty line>    |
#               put a # before each digit and at the end of the string 
{`\d            Loop:|
$*_                 Replace each digit with the corrisponding number of _
1`_                 |
n_                  Add an 'n' before the first _
__                  |
1                   Division by 2 (two _s become a 1)
_#                  |
#5                  Wherever there is a remainder, add 5 to the next digit
}`5$                |
                    Remove the final 5 you get when you divide odd numbers
n               Return the number of 'n's in the string

Wypróbuj online!

Ruby, 19 16 bajtów

->n{"%b"%n=~/$/}

Dzięki Jordan za grę w golfa z 3 bajtów

Jolf, 2 bajty

lB

Wystarczy przekonwertować na plik binarny, a następnie znaleźć długość.

Julia 0.4 , 14 bajtów

!n=log2(2n)÷1

Wypróbuj online!

JavaScript ES6, 19 bajtów

a=>32-Math.clz32(a)

Math.clz32zwraca liczbę wiodących zerowych bitów w 32-bitowej binarnej reprezentacji liczby. Aby uzyskać wymaganą liczbę bitów, wystarczy odjąć tę liczbę od 32

f=
  a=>32-Math.clz32(a)
  

pre {
    display: inline;
}

<input id=x type="number" oninput="y.innerHTML = f(x.value)" value=128><br>
<pre>Bits needed: <pre id=y>8</pre></pre>

narzędzia bash / Unix, 16 bajtów

dc<<<2o$1n|wc -c

Zapisz to w skrypcie i przekaż dane wejściowe jako argument. Zostanie wydrukowana liczba bitów wymagana do przedstawienia tej liczby w systemie binarnym.

Oto wyjaśnienie:

dc jest kalkulatorem stosowym. Dane wejściowe, pogrupowane w tokeny, to:

2 - Naciśnij 2 na stosie.

o - Usuń wartość ze stosu (która wynosi 2) i ustaw ją jako bazę wyjściową (tak więc dane wyjściowe są teraz w formacie binarnym).

Wartość argumentu dla programu bash ($ 1) - Wciśnij ten argument na stos.

n - Usuń wartość ze stosu (która jest liczbą wejściową) i wydrukuj ją (binarnie, ponieważ jest to baza wyjściowa) bez końca nowej linii.

Więc polecenie dc wypisuje liczbę w formacie binarnym.

Dane wyjściowe dc są przesyłane do polecenia wc z opcją -c, która wypisuje liczbę znaków na wejściu.

Końcowym rezultatem jest wydrukowanie liczby cyfr w binarnej reprezentacji argumentu.

Arkusze Google, 15 bajtów

Pobiera dane wejściowe z komórki A1i dane wyjściowe do komórki zawierającej formułę

=Len(Dec2Bin(A1

lub

=Int(1+Log(A1,2

lub

=Int(Log(2*A1,2

Excel, 17 bajtów

Taki sam jak powyżej, ale sformatowany dla MS Excel

=Len(Dec2Bin(A1))

lub

=Int(1+Log(A1,2))

lub

=Int(Log(2*A1,2))

Pyth, 3 bajty

l.B

Zestaw testowy dostępny tutaj.

Wyjaśnienie

l.BQ    Q is implicitly appended
   Q    eval(input)
 .B     convert Q to binary string
l       len(.B(Q))

Galaretka, 2 bajty

BL

Konwertuje na binarne, znajduje długość.

C #, 63 45 31 bajtów

Zaoszczędzono 18 bajtów dzięki Loovjo i TuukkaX

Zaoszczędzono 14 bajtów dzięki Grax

 b=>1+(int)System.Math.Log(b,2);

Wykorzystuje to, że liczba dziesiętna n ma ⌊log2 (n) ⌋ + 1 bit, co jest opisane na tej stronie:

Liczba bitów w określonej liczbie całkowitej dziesiętnej

Dodatnia liczba całkowita n ma bity, gdy 2 ^ (b-1) ≤ n ≤ 2 ^ b - 1. Na przykład:

• 29 ma 5 bitów, ponieważ 16 ≤ 29 ≤ 31 lub 2 ^ 4 ≤ 29 ≤ 2 ^ 5 - 1
• 123 ma 7 bitów, ponieważ 64 ≤ 123 ≤ 127 lub 2 ^ 6 ≤ 123 ≤ 2 ^ 7 - 1
• 967 ma 10 bitów, ponieważ 512 ≤ 967 ≤ 1023 lub 2 ^ 9 ≤ 967 ≤ 2 ^ 10 - 1

W przypadku większych liczb możesz sprawdzić tabelę potęg dwóch, aby znaleźć kolejne moce, które zawierają twój numer.

Aby zobaczyć, dlaczego to działa, pomyśl na przykład o reprezentacjach binarnych liczb całkowitych od 2 ^ 4 do 2 ^ 5 - 1. Są to wartości od 10000 do 11111, wszystkie możliwe wartości 5-bitowe.

Korzystanie z logarytmów

Powyższą metodę można określić w inny sposób: liczba bitów jest wykładnikiem najmniejszej potęgi o wartości większej niż twoja liczba. Możesz to powiedzieć matematycznie jako:

bspec = ⌊log2 (n) ⌋ + 1

Ta formuła składa się z trzech części:

• log2 (n) oznacza logarytm w podstawie 2 z n, który jest wykładnikiem potęgi do której 2 jest podniesione, aby otrzymać n. Na przykład log2 (123) ≈ 6,9425145. Obecność części ułamkowej oznacza, że ​​n jest między potęgami dwóch.

• ⌊X⌋ to podłoga x, która jest liczbą całkowitą x. Na przykład ⌊6.9425145⌋ = 6. Można myśleć o ⌊log2 (n) ⌋ jako wykładniku największej potęgi dwóch w binarnej reprezentacji n.

• +1 przenosi wykładnik do następnej wyższej potęgi dwóch. Możesz pomyśleć o tym kroku jako uwzględniającym 2 ^ 0 miejsce twojej liczby binarnej, co daje ci całkowitą liczbę bitów. W naszym przykładzie jest to 6 + 1 = 7. Możesz mieć ochotę użyć funkcji pułapu - ⌈x⌉, która jest najmniejszą liczbą całkowitą większą lub równą x - do obliczenia liczby bitów jako takich:

bspec = ⌈log2 (n) ⌉

Nie udaje się to jednak, gdy n jest potęgą dwóch.

C #, 32 bajty

n=>Convert.ToString(n,2).Length;

Konwertuje parametr na ciąg binarny i zwraca długość ciągu.

Haskell, 20 bajtów

succ.floor.logBase 2

Tworzy funkcję, która pobiera podstawę logarytmu 2, podłogi i dodaje 1.

Befunge-93 , 23 21 bajtów

&>2# /# :_1>+#<\#1_.@

Befunge to język oparty na siatce 2D (chociaż używam tylko jednej linii).

&                      take integer input
 >2# /# :_             until the top of the stack is zero, halve and duplicate it
          1>+#<\#1_    find the length of the stack
                   .@  output that length as an integer and terminate the program

Wypróbuj online!

Meduza , 4 bajty

p#bi

Wypróbuj online!

Print ( p), długość ( #) reprezentacji binarnej ( b) wejścia ( i).

CJam , 5 bajtów

ri2b,

Wypróbuj online!

Odczytaj input ( r), przekonwertuj na liczbę całkowitą ( i), uzyskaj reprezentację binarną ( 2b), pobierz length ( ,).

Oktawa , 19 bajtów

@(x)ceil(log2(x+1))

Anonimowa funkcja, która dodaje 1, oblicza logarytm binarny i zaokrągla w górę.

Wypróbuj online!

QBIC , 18 bajtów

:{~2^q>a|_Xq\q=q+1

To niesamowite Mike! Ale jak to działa?

:        Read input as integer 'a'
{        Start an infinite DO-LOOP
~2^q>a   If 2 to the power of q (which is 1 by default) is greater than a
|_Xq     Then quit, printing q
\q=q+1   Else, increment q
[LOOP is closed implicitly by QBIC]

Java 8, 34 27 bajtów

Po raz pierwszy Java ma kilka przydatnych funkcji wbudowanych! Teraz potrzebujemy tylko krótszych nazw ...

x->x.toString(x,2).length()

Wypróbuj online!

Oczywiście możesz to zrobić bez wbudowanych funkcji ( patrz odpowiedź Snowmana ), ale dla większej liczby bajtów.

Oktawa, 19 bajtów

@(x)nnz(dec2bin(x))    % or
@(x)nnz(de2bi(x)+1)    % or
@(x)nnz(de2bi(x)<2)    % or
@(x)numel(de2bi(x))    % or
@(x)rows(de2bi(x'))

Oktawa ma dwie funkcje do konwersji liczb dziesiętnych na liczby binarne.

dec2binkonwertuje liczbę na ciąg znaków 1i 0(wartości ASCII 48i 49). Długość łańcucha będzie równa niezbędnej liczbie bitów, chyba że określono inaczej. Ponieważ znaki 1i 0są niezerowe, możemy użyć nnz, aby znaleźć szereg elementów, takich jak ten: @(x)nnz(dec2bin(x)). Jest to 19 bajtów, więc jest powiązany z inną odpowiedzią Luisa Mendo Octave .

Czy możemy to zrobić lepiej de2bi?

de2bijest funkcją, która zwraca liczby binarne jako wektor z liczbami 1i 0jako liczby całkowite, a nie znaki. de2bijest oczywiście dwa bajty krótszy niż dec2bin, ale nie możemy już używać nnz. My może używać nnzgdybyśmy albo dodawać 1do wszystkich elementów, lub robi to w logiczną wektora z tylko truewartości. @(x)nnz(de2bi(x)+1)i @(x)nnz(de2bi(x)<2)oba mają 19 bajtów. Użycie numelda nam również 19 bajtów,@(x)numel(de2bi(x)) .

rowsjest o jeden bajt krótszy niż numel, ale de2bizwraca wektor poziomy, więc musi zostać transponowany. @(x)rows(de2bi(x)')akurat jest też 19 bajtów.

Pyke, 3 bajty

b2l

Wypróbuj tutaj!

Retina ,  44  23 bajtów

Wymaga zbyt dużej ilości pamięci, aby działać dla dużych wartości wejściowych. Konwertuje na unary, a następnie wielokrotnie dzieli przez 2, licząc ile razy, aż osiągnie zero. Liczba bajtów zakłada kodowanie ISO 8859-1.

.*
$*
+`^(1+)1?\1
$1_
.

Wypróbuj online