Aby znaleźć twardość cyfrową liczby całkowitej, weź jej reprezentację binarną i policz, ile razy wiodący i końcowy 1można usunąć, dopóki nie zacznie się lub nie zakończy na 0. Całkowita liczba usuniętych bitów to jego twardość cyfrowa.

To dość dziwne wytłumaczenie - podzielmy to na działający przykład.

W tym przykładzie użyjemy liczby 3167. Binarnie jest to:

110001011111

(Należy pamiętać, że podczas konwersji na binarną należy pamiętać o usunięciu wiodących zer)

Nie zaczyna się i nie kończy 0, więc usuwamy 1 parę bitów:

1  1000101111  1

I kolejny:

11  00010111  11

Ale teraz na początku jest 0, więc nie możemy już usunąć 1par. W sumie usunęliśmy 4 bity, a więc 4 to twardość cyfrowa 3167.

Jednak w przypadku liczb, które można zapisać jako 2 ⁿ -1 dla dodatniej n (tj. Zawierają tylko 1reprezentację binarną), 0 nigdy nie zostanie osiągnięte, więc wszystkie bity można usunąć. Oznacza to, że twardość jest po prostu liczbą bitową liczby całkowitej.

Wyzwanie

Twoim zadaniem jest napisanie programu lub funkcji, która przy nieujemnej liczbie całkowitej n >= 0określa jej twardość cyfrową.

Możesz przesłać pełny program wykonujący operacje we / wy lub funkcję zwracającą wynik. Przesłanie powinno działać w przypadku wartości nmieszczących się w standardowym zakresie liczb całkowitych w Twoim języku.

Przypadki testowe

Powiadom mnie, jeśli któreś z nich są niepoprawne lub jeśli chcesz zasugerować jakieś przypadki brzegowe do dodania.

0     -> 0
1     -> 1
8     -> 0
23    -> 2
31    -> 5
103   -> 4
127   -> 7
1877  -> 2
2015  -> 10

Oto nierozwinięte rozwiązanie Pythona, którego użyłem do wygenerowania tych przypadków testowych (nie ma gwarancji, że nie zawiera błędów):

def hardness(num) -> int:
    binary = bin(num)[2:]

    if binary.count('0') == 0:
        return num.bit_length()

    revbin = binary[::-1]

    return min(revbin.find('0'), binary.find('0')) * 2

Galaretka , 11 10 bajtów

BµQL××Ṛa\S

Wypróbuj online!

Jak to działa

BµQL××Ṛa\S  Main link. Argument: n

B           Binary; convert n to base 2.
 µ          Begin a new, monadic chain. Argument: A (array of binary digits)
  Q         Unique; deduplicate the digits.
   L        Length; count the unique digits.
    ×       Multiply each digit by the result.
     ×Ṛ     Multiply the results by reversed A.
       a\   Cumulative reduce by logical AND.
            This zeroes out all elements after the first zero.
         S  Compute the sum of the result.

Python , 76 69 68 63 62 60 57 bajtów

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

Wypróbuj online!

Jak to działa

Jest to rozwiązanie rekurencyjne, które przyjmuje dane wejściowe n i stale zwiększa k - zaczynając od 0 - podczas gdy zarówno LSB _k (n) (bit o indeksie k od prawej), jak i MSB _k (n) (bit o indeksie k od lewej) są ustawione. Po zakończeniu zwraca k, jeśli wszystkie bity n są ustawione, a 2k, jeśli nie.

Zacznijmy od przepisania lambda f jako funkcji o nazwie F , ze zmienną pomocniczą t .

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

Przy każdym wywołaniu F , najpierw przesuwamy bitem n łącznie k jednostek w prawo i zapisujemy wynik w t . W ten sposób LSB ₀ (t) = LSB _k (n) , więc t jest nieparzyste wtedy i tylko wtedy, gdy ustawiono LSB _k (n) .

Ustalenie, czy MSB _k (n) jest ustawione, jest nieco trudniejsze; właśnie to n & t > t >> 1osiąga. Aby zilustrować, jak to działa, rozważmy liczbę całkowitą n = 1αβγδεζη ₂ o długości bitu 8 i przeanalizujemy wywołanie funkcji F (n, 3) , tj. K = 3 .

Próbujemy ustalić, czy MSB ₃ (n) = γ jest ustawiony, badając wartość prawdziwości porównania (n & t> t >> 1) = (1αβγδεζη ₂ i 1αβγδ ₂ > 1αβγ ₂ ) . Sprawdźmy zaangażowane liczby całkowite.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

Twierdzimy, że γ = 1 wtedy i tylko wtedy, gdy n & t> t >> 1 .

• Jeśli γ = 1 , to n & t ma długość bitu 5, zaś t >> 1 ma długość bitu 4 , więc n & t> t >> 1 .

  Dowodzi to, że γ = 1 implikuje n & t> t >> 1 .

• Jeśli n & t> t >> 1 , istnieją dwie opcje: albo γ = 1, albo γ = 0 . W pierwszym przypadku nic nie zostało do udowodnienia.

  W drugim przypadku ma to αβγδ ₂ ≥ n t t> >> 1 = 1αβγ ₂ .

  Od αβγδ ₂ > 1αβγ ₂ , musimy MSB ₀ (αβγδ ₂ ) ≥ MSB ₀ (1αβγ ₂ ) , co oznacza, że a = 1 .

  W ten sposób 1βγδ ₂ > 11βγ ₂ , więc musimy mieć MSB ₁ (1βγδ ₂ ) ≥ MSB ₁ (11βγ ₂ ) , co oznacza, że p = 1 .

  To z kolei oznacza, że 11γδ ₂ > 111γ ₂ . Pamiętając, że γ = 0 w drugim przypadku, otrzymujemy nierówność 110δ ₂ > 1110 ₂ , co jest fałszem, ponieważ MSB ₂ (110δ ₂ ) = 0 <1 = MSB ₂ (1110 ₂ ) .

  Zatem możliwy jest tylko pierwszy przypadek, a n & t> t >> 1 implikuje γ = 1 .

Reasumując, jeśli zarówno LSB _k (n) i MSB _k (n) są ustawione, t będzie dziwne i n t> t >> 1 będzie prawda , więc t (n & t> t >> 1) będzie wydajność 1 . Jeśli jednak LSB _k (n) lub MSB _k (n) nie jest ustawione (lub jeśli oba są), t będzie parzyste lub n & t> t >> 1 będzie False , więc t & (n & t> t> > 1) da 0 .

Wywołanie F z jednym argumentem inicjuje k = 0 . Podczas gdy warunek, który omówiliśmy wcześniej, andjest spełniony, wykonywany jest kod after , który (między innymi) rekurencyjnie wywołuje F z przyrostem k .

Po rozbrojeniu LSB _k (n) lub MSB _k (n) warunek kończy się niepowodzeniem, a F (n, k) zwraca 0 . Każde z poprzednich wywołań funkcji k dodaje (n & (n + 1)> 0) + 1 do F (n, k) = 0 , więc F (n) zwraca ((n & (n + 1)> 0) + 1) k .

Teraz, jeśli wszystkie bity n są równe (tj. Jeśli n jest albo 0 albo wszystkie jego bity są ustawione), n + 1 nie będzie mieć żadnych bitów wspólnych z n , więc n & (n + 1) = 0 i F (n) zwraca k . Jeśli jednak n ma ustawione i nieuzbrojone bity, n & (n + 1)> 0, a F (n) zwraca 2k .

MATL , 13 12 bajtów

Btv`6L&)}x@q

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Kod powtarza każdą cyfrę binarną i liczy, ile razy można usunąć dwie zewnętrzne.

B        % Input number (implicit). Horizontal vector of binary digits
tv       % Duplicate and concatenate vertically
`        % Do...while
  6L&)   %   Flatten the array if needed (in column-major order), and split it
         %   into two subarrays: one with the inner entries, and another
         %   with the two outer entries. The latter will be used for deciding
         %   if the loop continues or is exited
}        % Finally (execute before exiting the loop)
  x      %   Delete last subarray of inner entries
  @q     %   Push last iteration index minus 1
         % End (implicit). The next iterarion is executed if the array at the
         % top of the stack is non-empty and only contains nonzero values. 
         % Otherwise the loop is exited, executing the "finally" block first
         % Display (implicit)

Python, 82 bajty

Wydaje mi się, że nadal można grać w golfa, ale spędziłem trochę czasu próbując różnych metod i to było najkrótsze.

def f(n):b=bin(n)[2:];x=min(b.find('0'),b[::-1].find('0'));print(x<0)*len(b)or x*2

Wypróbuj online

Chociaż działa to podobnie do programu Python OP, stworzyłem to przed opublikowaniem pytania, po przejrzeniu pytania w piaskownicy, które nie zawierało takiego programu.

Python 2, 66 bajtów

s=bin(input())[2:].split('0')
print len(min(s[-1],s[0]))<<1%len(s)

Dzieli binarną reprezentację danych wejściowych na porcje 1. Zlicza liczbę 1 w mniejszej z pierwszej i ostatniej porcji, a następnie podwaja ją, chyba że istnieje jedna porcja, która by się podwoiła.

PowerShell , 109 106 bajtów

$a=[convert]::ToString($args[0],2)-split0;(((($b=$a[0].length),$a[-1].length|sort)[0]*2),$b)[$a.count-eq1]

Wypróbuj online!

Zajmuje wejście $args[0], wykorzystuje połączenie .NET do convertniego toStringz bazy 2(czyli uczynić go binarne), a następnie -splitz którą napis na 0s, sklepy, które w $a. Ważne, aby pamiętać: wywołanie .NET nie zwraca zer wiodących, więc pierwszą cyfrą jest zawsze cyfra 1.

Istnieją zatem dwie możliwości - ciąg binarny jest wszystkim, lub było co najmniej jedno zero. Rozróżniamy te z pseudo-trójskładnikiem indeksowanym przez $a.count-eq1. Jeśli plik binarny ma co najmniej jedno zero, w lewym przypadku, bierzemy minimalną długość pierwszego [0]ciągu 1s i ostatniego [-1]ciągu (znalezionego do |sorttego czasu [0]). Im krótsza z nich, tym więcej par możemy usunąć, więc pomnożymy to przez 2. Zauważ, że jeśli oryginalny ciąg binarny kończy się na 0, jak na wejściu 8, to [-1].lengthrównież będzie 0(ponieważ jest to pusty ciąg), który po pomnożeniu 2jest nadal 0.

W przeciwnym razie, biorąc pod uwagę ciąg binarny wszystkie, bierzemy tylko $b(która wcześniej była ustawiona na długość pierwszego [0]ciągu, w tym przypadku całość ciągu binarnego).

W obu przypadkach wynik pozostaje w potoku, a dane wyjściowe są niejawne.

JavaScript (ES6), 57 bajtów

f=
n=>n.toString(2).replace(/^(1*)(.*(\1))?$/,'$1$3').length

<input oninput=o.value=1/this.value?f(+this.value):''><input id=o readonly>

Pobiera plik binarny i próbuje dopasować wszystkie 1slub, jeśli nie, taką samą liczbę wiodących i końcowych 1s.

Siatkówka , 48 bajtów

.+
$*
+`(1+)\1
$1o
o1
1
m(+`^1(.*)1$
xx¶$1
x|^1$

Wypróbuj online

Wyjaśnienie:

.+              # Convert to unary
$*
+`(1+)\1        # Convert to binary (but with `o` instead of `0` -- it's shorter)
$1o
o1
1
m(+`^1(.*)1$    # Replace pairs of surrounding ones with `xx`
xx¶$1
x|^1$,          # Count x's, including the possibility of a single remaining `1`

C #, 133 bajty

Funkcja, która zwraca twardość. Bierze liczbę całkowitą z argumentu.

int h(int b){var n=Convert.ToString(b,2);for(b=0;;){if(n[0]+n[n.Length-1]==98)n=n.Substring(1,n.Length-2);else break;b+=2;}return b;}

Cóż, dzisiaj dowiedziałem się '1' + '1' = 98w C #.

C, 89 88 85 bajtów

Zapisano dwa bajty dzięki @FlipTack wskazując na bezużyteczną deklarację.

Zadzwoń f()z numerem do przetestowania, wynik jest zwracany z funkcji.

t,h;f(l){for(t=l;t&&~t&1<<30;t*=2);for(h=0;t&1<<30&&l&1;t*=2,l/=2)++h;return h<<!!l;}

Wypróbuj na ideone .

JavaScript (ES6), 59 58 bajtów

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

Przypadki testowe

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

console.log(
  [0, 1, 8, 23, 31, 103, 127, 1877, 2015].map(
    n => n + ' -> ' + f(n)
  ).join('\n')
)

Galaretka , 14 bajtów

Eo2
BµŒg.ịṂS×Ç

Wypróbuj online!

C, 137 132 122 119 117 114 98 94 92 87 85 Bajtów

Czas zacząć grać w golfa B-)

i,j;f(n){for(i=1<<30;i&~n;i/=2);for(j=0;n&i;n/=2,i/=4)j+=~n&1?i=0:2;return j-=n<1*j;}

Oto dowód

main()
{
  printf("%d %d\n", 0, f(0));
  printf("%d %d\n", 1, f(1));
  printf("%d %d\n", 8, f(8));
  printf("%d %d\n", 23, f(23));
  printf("%d %d\n", 31, f(31));
  printf("%d %d\n", 103, f(103));
  printf("%d %d\n", 127, f(127));
  printf("%d %d\n", 1877, f(1877));
  printf("%d %d\n", 2015, f(2015));
  printf("%d %d\n", 3167, f(3167));
} 

i wynik;

0 0
1 1
8 0
23 2
31 5
103 4
127 7
1877 2
2015 10
3167 4 

Java (OpenJDK) , 181 156 150 bajtów

n->{int i=0;String s=n.toString(n,2);if(s.matches("1*"))i=s.length();else for(;!s.matches("(.*0)|(0.*)");s=s.substring(1,s.length()-1))i+=2;return i;}

Wypróbuj online!

Mathematica, 63 56 bajtów

(2-Min[l=#~IntegerDigits~2])Min[Tr/@Split[l][[{1,-1}]]]&

Wyjaśnienie

l=#~IntegerDigits~2

Wygeneruj reprezentację danych wejściowych base-2, opakowaną w a List. Przechowuj to wl

(2-Min[...])

Jeśli min. Element lto 1, wyślij 1. Jeśli nie, wyślij 2. Pomnóż to przez ...

Split[l]

Podziel lna przebiegi.

... [[{1,-1}]]

Weź pierwszy i ostatni element.

Tr/@ ...

Weź sumę obu.

Min[ ... ]

Znajdź mniejszy między nimi.

(Pomnóż pierwszy wynik (1 lub 2) przez ten wynik).

Oktawa, 56 54 bajtów

 @(n)cummin(d=dec2bin(n)-48)*cummin(flip(d))'*2^!all(d)

Wypróbuj online!

Wyjaśnienie:

d=dec2bin(n)-48

binarna reprezentacja n

cumd= cummin(d);
cumfd = cummin(flip(d));

Weź skumulowaną min d i skumulowaną min odwróconejd

res = cumd * cumfd ';

wykonaj mnożenie macierzy

out = res*2^!all(d)

pomnóż przez 2, jeśli wszystkie cyfry to 1;

Pyth, 18 bajtów

?*FJjQ2lJyhSxR0_BJ

Program, który pobiera liczbę całkowitą i wypisuje wynik.

Zestaw testowy (pierwsza linia do formatowania)

Jak to działa

?*FJjQ2lJyhSxR0_BJ  Program. Input: Q
?                   If
  F                 reducing
    jQ2             the binary representation of Q as a list
   J                (store in J)
 *                  by multiplication is truthy:
       lJ            Yield len(J)
                    Else:
          hS         Yield the minimum
            xR0      of the first index of zero
               _BJ   in J and its reverse
         y           * 2
                    Implicitly print

APL, 26 bajtów

+/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢

Przypadki testowe:

      ( +/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢ ) ¨ 0 1 8 23 31 103 127 1877 2015    
0 1 0 2 5 4 7 2 10

Wyjaśnienie:

+ / ∘ (∧ \ ≢ ↑ (∊⊢ (, ∧∧) ¨⌽)) 2⊥⍣¯1⊢

                         ⊢ wejście
                    2⊥⍣¯1 konwersja do reprezentacji binarnej
   ()
        (⊢ ¨⌽) dla każdego bitu i odpowiadającego mu bitu po drugiej stronie
            (∧) weź logikę i oba bity,
             , sporządzić listę obu bitów,
              Take następnie weź listę i, a następnie i
         ∊ spłaszcz wynikową tablicę
      ≢ ↑ bierze tylko pierwsze N ​​bitów, gdzie N to
                                długość oryginalnej listy bitów
    Take \ bierz działającą logikę i (pozostawiając tylko
                                te początkowe)
+ / ∘ zsumuj je

J, 22 bajty

(#<.2*(<.&(#.~)|.))@#:

Jest to oparte na zgrabnej sztuczce wyuczonej z tego wyzwania .

Wypróbuj online!

Wyjaśnienie

(#<.2*(<.&(#.~)|.))@#:  Input: integer n
                    #:  Binary digits of n
(                 )@    Operate on those digits D
               |.         Reverse D
       <.                 Take the minimum of
         &(#.~)           the "trailing truths" of D and reverse(D)
    2*                    Multiply by 2
 #                        The length of D
  <.                      Minimum of length and the previous result

PHP, 83 74 bajty

3 + 6 bajtów zapisanych przez Jörga

<?=(~$s=decbin($argn))[$a=strspn($s,1)]?min($a,strspn(strrev($s),1))*2:$a;

pobiera dane wejściowe z STDIN; biegać z -nR.

awaria

<?=                     # print ...
(~
    $s=decbin($argn)        # $s = binary representation of input
)[
    $a=strspn($s,1)         # $a = number of leading `1`s
]                           # if $s has more than $a digits,
?   min($a,                     # 2. minimum of $a and
        strspn(strrev($s),1)    # 1. number of trailing `1`s
    )*2                         # 3. *2
:   $a                      # else $a (==strlen)

JavaScript (ES6), 83 bajtów

f=x=>(y=x.toString(2),y.match(/^1*$/)?y:([s,e]=y.match(/^1*|1*$/g),s<e?s:e)).length

Nie golfowany:

function f(n) {
    var binStr = n.toString(2);
    if(binStr.match(/^1*$/)) {
        // If binary representation is all 1s, return length of binary
        return binStr.length;
    } else {
        // Grab the starting and ending 1s in the binary representation
        var [start1s, end1s] = binStr.match(/^1*|1*$/g);
        var startHardness = start1s.length;
        var endHardness = end1s.length;
        return Math.min(startHardness, endHardness);
    }
}

Mathematica, 62 bajty

(h=0;#~IntegerDigits~2//.{{1,m___,1}:>(h+=2;{m}),{1}:>h++};h)&

Czysta funkcja, gdzie #reprezentuje pierwszy argument.

(h=0;...;h)&ustawia h=0, robi kilka rzeczy ..., a następnie zwraca h(twardość). Spójrzmy na kilka rzeczy:

#~IntegerDigits~2                                     Binary representation of the input
                 //.                                  Apply the following list of rules repeatedly until there is no change
                    {                                 Start of the list of rules
                     {1,m___,1}                       If you see a list starting and ending with 1 with the sequence m (possibly empty) in between
                               :>(h+=2;{m}),            replace it with just {m} after incrementing h twice.
                                            {1}       If you see the singleton list {1}
                                               :>h++    replace it with h, then increment h.
                                                    } End of the list of rules

Dzięki Gregowi Martinowi za zapoznanie mnie z tą sztuczką .

Haskell , 94 92 bajty

b 0=[]
b n=mod n 2:b(div n 2)
h n|(c,_:_)<-span(>0)$zipWith(*)n$reverse n=c++c|1<3=n
sum.h.b

Wypróbuj online! Stosowanie:

Prelude> sum.h.b $ 3167
4

Objaśnienie:
b konwertuje liczbę na binarną i zwraca listę zer i pierwszych z najmniej znaczącym bitem. W htej lista jest odwrócona i elementarnie pomnożona z pierwotną listą, a następnie span(>0)dzieli się po początkowych 1s:

       b 3167 = [1,1,1,1,1,0,1,0,0,0,1,1] = n
    reverse n = [1,1,0,0,0,1,0,1,1,1,1,1] = m
zipWith(*)n m = [1,1,0,0,0,0,0,0,0,0,1,1] = z
   span(>0) z = ([1,1],[0,0,0,0,0,0,0,0,1,1])

Powstała krotka jest dopasowywana do wzorca, (c,_:_)gdzie _:_pasuje do dowolnej niepustej listy, więc c = [1,1]. Ponieważ bajty są usuwane z przodu iz tyłu, c++c = [1,1,1,1]są zwracane i ostatecznie sumowane, aby uzyskać twardość cyfrową .

Jeśli druga lista krotki jest pusta, wówczas reprezentacja binarna zawiera tylko je, a ich liczba to twardość cyfrowa. Dopasowanie wzorca zakończyło się niepowodzeniem, hpo prostu zwraca n, co jest ponownie sumowane.

Perl, 61 bajtów

sub f{$_=sprintf('%b',pop);length(/0/?/^(1+).*\1$/&&$1x2:$_)}

Sercem tego jest wyrażenie regularne, w /^(1+).*\1$/którym odpowiedź stanowi dwukrotność długości $1. Reszta kodu jest narzutem i zajmuje się specjalnym przypadkiem wszystkich 1.

PHP, 65 bajtów

<?=strlen(preg_filter('#^(1*)(.*(\1))?$#',"$1$3",decbin($argn)));

Wersja online

CJam, 14 bajtów

ri2b_0#\W%0#e<

Wyjaśnienie:

ri e# Read integer:      | 3167
2b e# Convert to binary: | [1 1 0 0 0 1 0 1 1 1 1 1]
_  e# Duplicate:         | [1 1 0 0 0 1 0 1 1 1 1 1] [1 1 0 0 0 1 0 1 1 1 1 1]
0# e# Index of first 0:  | [1 1 0 0 0 1 0 1 1 1 1 1] 2
\  e# Swap:              | 2 [1 1 0 0 0 1 0 1 1 1 1 1]
W% e# Reverse:           | 2 [1 1 1 1 1 0 1 0 0 0 1 1]
0# e# Index of first 0:  | 2 5
e< e# Minimum:           | 2