Liczba całkowita jest obciążeniem binarnym, jeśli jej reprezentacja binarna zawiera więcej 1niż 0s, ignorując początkowe zera. Na przykład 1 jest obciążeniem binarnym, ponieważ jego reprezentacja binarna jest po prostu 1, jednak 4 nie jest obciążeniem binarnym, tak jak jego reprezentacja binarna 100. W przypadku remisu (na przykład 2, z reprezentacją binarną 10), liczba nie jest uważana za binarną.

Biorąc pod uwagę dodatnią liczbę całkowitą jako dane wejściowe, wypisz prawdziwą wartość, jeśli jest binarnie ciężka, i wartość falsey, jeśli nie jest.

Przypadki testowe

Format: input -> binary -> output

1          ->                                1 -> True
2          ->                               10 -> False
4          ->                              100 -> False
5          ->                              101 -> True
60         ->                           111100 -> True
316        ->                        100111100 -> True
632        ->                       1001111000 -> False
2147483647 ->  1111111111111111111111111111111 -> True
2147483648 -> 10000000000000000000000000000000 -> False

Punktacja

To jest golf golfowy, więc wygrywa najmniej bajtów w każdym języku

Kod maszynowy x86, 15 14 bajtów

F3 0F B8 C1 0F BD D1 03 C0 42 2B D0 D6 C3

Jest to funkcja wykorzystująca konwencję wywoływania __fastcall Microsoftu (pierwszy i jedyny parametr w ecx, zwracana wartość w eax, callee ma prawo zamykać edx), chociaż może być w trywialny sposób modyfikowana dla innych konwencji wywoływania, które przekazują argumenty w rejestrach.

Zwraca 255 jako prawdę, a 0 jako falsey.

Używa nieudokumentowanego (ale szeroko obsługiwanego) kodu operacyjnego salc.

Demontaż poniżej:

;F3 0F B8 C1 
  popcnt eax, ecx ; Sets eax to number of bits set in ecx

;0F BD D1
  bsr edx, ecx    ; Sets edx to the index of the leading 1 bit of ecx

;03 C0
  add eax, eax

;42
  inc edx

;2B D0
  sub edx, eax

  ; At this point, 
  ;   edx = (index of highest bit set) + 1 - 2*(number of bits set)
  ; This is negative if and only if ecx was binary-heavy.

;D6
  salc           ; undocumented opcode. Sets al to 255 if carry flag 
                 ; is set, and to 0 otherwise. 

;C3
  ret

Wypróbuj online!

Podziękowania dla Petera Cordesa za sugestię zastąpienia lzcntgo bsr.

Galaretka , 5 bajtów

Bo-SR

Daje niepuste wyjście (prawda) lub puste wyjście (fałsz).

Wypróbuj online!

Jak to działa

Bo-SR  Main link. Argument: n

B      Binary; convert n to base 2.
 o-    Compute the logical OR with -1, mapping 1 -> 1 and 0 -> -1.
   S   Take the sum s. We need to check if the sum is strictly positive.
    R  Range; yield [1, ..., s], which is non-empty iff s > 0.

Python 2 , 35 bajtów

lambda n:max('10',key=bin(n).count)

Wypróbuj online!

Stara odpowiedź, 38 bajtów

^{Wyjścia 0jak falsy i -2czy -1jako truthy}

lambda n:~cmp(*map(bin(n).count,'10'))

Wypróbuj online!

Oktawa , 18 bajtów

@(n)mode(de2bi(n))

TIO nie działa, ponieważ zestaw narzędzi do komunikacji nie jest dołączony. Można to przetestować w Octave-Online .

Jak to działa:

de2bikonwertuje liczbę dziesiętną na binarny wektor numeryczny, a nie ciąg, jak to dec2binrobi.

modezwraca najczęstszą cyfrę w wektorze. Domyślnie jest najniższy w przypadku remisu.

@(n)                % Anonymous function that takes a decimal number as input 'n'
    mode(        )  % Computes the most frequent digit in the vector inside the parentheses
         de2bi(n)   % Converts the number 'n' to a binary vector

JavaScript (ES6), 36 34 bajtów

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0

MATL , 3 bajty

BXM

Wypróbuj online!

Naprawdę nie znam MATL-a, zauważyłem, że to modemoże zadziałać w odpowiedzi Octave na alphalpha i doszedłem do wniosku, że w MATL-ie jest jakiś odpowiednik.

B   ' binary array from input
 XM ' value appearing most.  On ties, 0 wins

Mathematica, 22 bajty

Oszczędność jednego bajtu dzięki @MartinEnder i @JungHwanMin .

#>#2&@@#~DigitCount~2&

Brachylog , 6 bajtów

ḃọtᵐ>₁

Wypróbuj online!

Wyjaśnienie

Example input: 13

ḃ        Base (default: binary): [1,1,0,1]
 ọ       Occurences:             [[1,3],[0,1]]
  tᵐ     Map Tail:               [3,1]
    >₁   Strictly decreasing list

Ponieważ ḃnigdy nie ujednolici wyników za pomocą listy cyfr z zerami wiodącymi, wiemy, że wystąpienia 1zawsze będą pierwsze, a wystąpienia 0zawsze będą drugie po ọ.

Python 3 ,  44  (dzięki @ c-mcavoy) 40 bajtów

lambda n:bin(n).count('0')<len(bin(n))/2

Wypróbuj online!

C (gcc) , 51 48 41 40 bajtów

i;f(n){for(i=0;n;n/=2)i+=n%2*2-1;n=i>0;}

Wypróbuj online!

R , 54 53 51 bajtów

-1 bajt dzięki Maxowi Lawnboyowi

n=scan();d=floor(log2(n))+1;sum(n%/%2^(0:d)%%2)*2>d

czyta ze standardowego; zwraca TRUEbinarne liczby ciężkie. dto liczba cyfr binarnych; sum(n%/%2^(0:d)%%2oblicza sumę cyfr (tj. liczbę jedności).

Wypróbuj online!

kod maszynowy x86_64, 23 22 21 bajtów

31 c0 89 fa 83 e2 01 8d 44 50 ff d1 ef 75 f3 f7 d8 c1 e8 1f c3

Zdemontowano:

  # zero out eax
  xor  %eax, %eax
Loop:
  # copy input to edx
  mov  %edi, %edx
  # extract LSB(edx)
  and  $0x1, %edx
  # increment(1)/decrement(0) eax depending on that bit
  lea -1(%rax,%rdx,2), %eax
  # input >>= 1
  shr  %edi
  # if input != 0: repeat from Loop
  jnz  Loop

  # now `eax < 0` iff the input was not binary heavy,
  neg %eax
  # now `eax < 0` iff the input was binary heavy (which means the MSB is `1`)
  # set return value to MSB(eax)
  shr  $31, %eax
  ret

Dzięki @Ruslan, @PeterCordes za -1bajt!

Wypróbuj online!

Perl 6 ,  32  30 bajtów

{[>] .base(2).comb.Bag{qw<1 0>}}

Sprawdź to

{[>] .polymod(2 xx*).Bag{1,0}}

Sprawdź to

Rozszerzony:

{      # bare block lambda with implicit parameter ｢$_｣

  [>]  # reduce the following with &infix:« > »

    .polymod(2 xx *) # turn into base 2 (reversed) (implicit method call on ｢$_｣)
    .Bag\            # put into a weighted Set
    { 1, 0 }         # key into that with 1 and 0
                     # (returns 2 element list that [>] will reduce)
}

Mądry , 40 39 bajtów

::^?[:::^~-&[-~!-~-~?]!~-?|>]|:[>-?>?]|

Wypróbuj online!

Wyjaśnienie

::^?                                      Put a zero on the bottom
    [                                     While
     :::^~-&                              Get the last bit
            [-~!-~-~?]!~-?|               Increment counter if 0 decrement if 1
                           >              Remove the last bit
                            ]|            End while
                              :[>-?>?]|   Get the sign

Haskell, 41 34

g 0=0
g n=g(div n 2)+(-1)^n
(<0).g

Jeśli njest nieparzysty, weź, -1jeśli to jest parzyste, weź 1. Dodaj połączenie rekurencyjne za pomocą n/2i zakończ, jeśli n = 0. Jeśli wynik jest mniejszy niż 0liczba jest binarna.

Wypróbuj online!

Edycja: @ Ørjan Johansen znalazł kilka skrótów i zapisał 7 bajtów. Dzięki!

Siatkówka , 37 34 bajtów

.+
$*
+`(1+)\1
$1@
@1
1
+`.\b.

1+

Wypróbuj online! Link zawiera mniejsze przypadki testowe (w większych prawdopodobnie zabraknie pamięci). Edycja: Zapisano 3 bajty dzięki @MartinEnder. Objaśnienie: Pierwszy etap konwertuje z postaci dziesiętnej na unarną, a kolejne dwa stopnie konwertują z unaryjnej na binarną (jest to prawie prosto z jednostronnej strony arytmetycznej na wiki Retina, tyle że używam @zamiast niej 0). Trzeci etap szuka pary znaków niepodobnych, które mogłyby być @1albo 1@i usuwa je, dopóki żaden pozostają. Ostatni etap sprawdza następnie pozostałe 1s.

R , 43 bajty

max(which(B<-intToBits(scan())>0))/2<sum(B)

Wypróbuj online!

             intToBits(scan())              # converts to bits
          B<-                 >0            # make logical and assign to B
max(which(                      ))/2        # get the length of the trimmed binary and halve
                                    <sum(B) # test against the sum of bits

Kotlin , 50 bajtów

{i:Int->i.toString(2).run{count{it>'0'}>length/2}}

Lambda typu niejawnego (Int) -> Boolean. Wersja 1.1 i wyższa tylko ze względu na użycie Int.toString(radix: Int).

Niestety środowisko uruchomieniowe TIO Kotlin wydaje się być 1.0.x, więc tutaj jest smutny pies zamiast linku TIO:

Pyth, 9 7 bajtów

ehc2S.B

Wypróbuj tutaj.

-2 dzięki FryAmTheEggman .

R, 39 37 bajtów

sum(intToBits(x<-scan())>0)>2+log2(x)

Jest to kombinacja metod używanych przez @MickyT i @Giuseppe, oszczędzając kolejne kilka bajtów.

sum(intToBits(x) > 0)zlicza liczbę 1bitów i 2+log2(x)/2stanowi połowę całkowitej liczby bitów po zaokrągleniu w dół. Nie musimy zaokrąglać w dół z powodu zachowania, gdy obie wartości są równe.

C # (.NET Core) , 62 , 49 bajtów

Bez LINQ.

EDYCJA: dana z 13-bajtowym golfem zmieniającym czas na rekurencyjny i zwracającym bool zamiast liczby całkowitej.

x=>{int j=0;for(;x>0;x/=2)j+=x%2*2-1;return j>0;}

Wypróbuj online!

Regex (ECMAScript), 85 73 71 bajtów

^((?=(x*?)\2(\2{4})+$|(x*?)(\4\4xx)*$)(\2\4|(x*)\5\7\7(?=\4\7$\2)\B))*$

Wypróbuj online!

_{^{wyjaśnienie przez Deadcode}}

Wcześniejsza 73-bajtowa wersja została wyjaśniona poniżej.

^((?=(x*?)\2(\2{4})+$)\2|(?=(x*?)(\4\4xx)*$)(\4|\5(x*)\7\7(?=\4\7$)\B))+$

Z powodu ograniczeń wyrażenia regularnego ECMAScript skuteczną taktyką jest często przekształcanie kroku numer jeden na raz, przy zachowaniu wymaganej właściwości niezmiennej na każdym kroku. Na przykład, aby przetestować idealny kwadrat lub potęgę 2, zmniejsz liczbę, zachowując kwadrat lub potęgę 2 (odpowiednio) na każdym kroku.

Oto, co robi to rozwiązanie na każdym kroku:

111100101$ones>zeroes$$1$

$ones>zeroes⇔ones-1>zeroes-1$

Gdy te powtarzające się kroki nie mogą pójść dalej, wynikiem końcowym będzie ciągły ciąg 1bitów, który jest ciężki i wskazuje, że pierwotna liczba była również ciężka, lub potęga 2, co wskazuje, że pierwotna liczba nie była ciężka.

I oczywiście, chociaż te kroki są opisane powyżej w kategoriach manipulacji typograficznych na binarnej reprezentacji liczby, w rzeczywistości są one realizowane jako jednowymiarowa arytmetyka.

# For these comments, N = the number to the right of the "cursor", a.k.a. "tail",
# and "rightmost" refers to the big-endian binary representation of N.
^
(                          # if N is even and not a power of 2:
    (?=(x*?)\2(\2{4})+$)   # \2 = smallest divisor of N/2 such that the quotient is
                           # odd and greater than 1; as such, it is guaranteed to be
                           # the largest power of 2 that divides N/2, iff N is not
                           # itself a power of 2 (using "+" instead of "*" is what
                           # prevents a match if N is a power of 2).
    \2                     # N = N - \2. This changes the rightmost "10" to a "01".
|                          # else (N is odd or a power of 2)
    (?=(x*?)(\4\4xx)*$)    # \4+1 = smallest divisor of N+1 such that the quotient is
                           # odd; as such, \4+1 is guaranteed to be the largest power
                           # of 2 that divides N+1. So, iff N is even, \4 will be 0.
                           # Another way of saying this: \4 = the string of
                           # contiguous 1 bits from the rightmost part of N.
                           # \5 = (\4+1) * 2 iff N+1 is not a power of 2, else
                           # \5 = unset (NPCG) (iff N+1 is a power of 2), but since
                           #   N==\4 iff this is the case, the loop will exit
                           #   immediately anyway, so an unset \5 will never be used.
    (
        \4                 # N = N - \4. If N==\4 before this, it was all 1 bits and
                           # therefore heavy, so the loop will exit and match. This
                           # would work as "\4$", and leaving out the "$" is a golf
                           # optimization. It still works without the "$" because if
                           # N is no longer heavy after having \4 subtracted from it,
                           # this will eventually result in a non-match which will
                           # then backtrack to a point where N was still heavy, at
                           # which point the following alternative will be tried.
    |
        # N = (N + \4 - 2) / 4. This removes the rightmost "01". As such, it removes
        # an equal number of 0 bits and 1 bits (one of each) and the heaviness of N
        # is invariant before and after. This fails to match if N is a power of 2,
        # and in fact causes the loop to reach a dead end in that case.
        \5                 # N = N - (\4+1)*2
        (x*)\7\7(?=\4\7$)  # N = (N - \4) / 4 + \4
        \B                 # Assert N > 0 (this would be the same as asserting N > 2
                           # before the above N = (N + \4 - 2) / 4 operation).
    )
)+
$       # This can only be a match if the loop was exited due to N==\4.

Regex (ECMAScript), 183 bajty

Był to kolejny interesujący problem do rozwiązania z wyrażeniem regularnym ECMA. „Oczywistym” sposobem na poradzenie sobie z tym jest policzenie liczby 1bitów i porównanie ich z całkowitą liczbą bitów. Ale nie można bezpośrednio liczyć rzeczy w wyrażeniu regularnym ECMAScript - brak trwałych odwołań zwrotnych oznacza, że ​​tylko jedna liczba może być modyfikowana w pętli, a na każdym kroku można ją tylko zmniejszyć.

Ten jednoargumentowy algorytm działa w następujący sposób:

1. Weź pierwiastek kwadratowy z największej potęgi 2, która pasuje do N, i zwróć uwagę, czy pierwiastek kwadratowy był idealny, czy też musiał zostać zaokrąglony w dół. Zostanie to wykorzystane później.
2. W pętli przesuń każdy najbardziej znaczący 1bit do najmniej znaczącej pozycji, w której jest 0bit. Każdy z tych kroków jest odejmowaniem. Na końcu pętli pozostała liczba (jak byłaby reprezentowana w postaci binarnej) to ciąg 1s bez 0s. Operacje te są faktycznie wykonywane jednostkowo; tylko koncepcyjnie są one wykonywane binarnie.
3. Porównaj ten „ciąg binarny 1s” z pierwiastkiem kwadratowym uzyskanym wcześniej. Jeśli pierwiastek kwadratowy musiał zostać zaokrąglony w dół, użyj jego podwójnej wersji. Zapewnia to, że „ciąg binarny 1s” musi mieć więcej niż połowę liczby cyfr binarnych niż N, aby możliwe było ostateczne dopasowanie.

Aby uzyskać pierwiastek kwadratowy, stosuje się wariant algorytmu mnożenia krótko opisany w moim wyrażeniu regularnym liczb Rocco . Aby zidentyfikować najmniej znaczący 0bit, zastosowano algorytm podziału krótko opisany w moim wyrażeniu regularnym wyrażenia regularnego . To są spoilery . Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samemu odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z listy zalecanych problemów oznaczonych spoilerem w tym wcześniejszym poście i samodzielnego wymyślenia matematycznych spostrzeżeń.

Bez zbędnych ceregieli wyrażenie regularne:

^(?=.*?(?!(x(xx)+)\1*$)(x)*?(x(x*))(?=(\4*)\5+$)\4*$\6)(?=(((?=(x(x+)(?=\10$))*(x*))(?!.*$\11)(?=(x*)(?=(x\12)*$)(?=\11+$)\11\12+$)(?=.*?(?!(x(xx)+)\14*$)\13(x*))\16)*))\7\4(.*$\3|\4)

Wypróbuj online!

# For the purposes of these comments, the input number = N.
^
# Take the floor square root of N
(?=
    .*?
    (?!(x(xx)+)\1*$)    # tail = the largest power of 2 less than tail
    (x)*?               # \3 = nonzero if we will need to round this square root
                        #      up to the next power of two
    (x(x*))             # \4 = potential square root; \5 = \4 - 1
    (?=
        (\4*)\5+$       # Iff \4*\4 == our number, then the first match here must result in \6==0
    )
    \4*$\6              # Test for divisibility by \4 and for \6==0 simultaneously
)
# Move all binary bits to be as least-significant as possible, e.g. 11001001 -> 1111
(?=
    (                                 # \7 = tool for making tail = the result of this move
        (
            (?=
                (x(x+)(?=\10$))*(x*)  # \11 = {divisor for getting the least-significant 0 bit}-1
            )
            (?!.*$\11)                # Exit the loop when \11==0
            (?=
                (x*)                  # \12 = floor((tail+1) / (\11+1)) - 1
                (?=(x\12)*$)          # \13 = \12+1
                (?=\11+$)
                \11\12+$
            )
            (?=
                .*?
                (?!(x(xx)+)\14*$)     # tail = the largest power of 2 less than tail
                \13                   # tail -= \13
                (x*)                  # \16 = tool to move the most-significant 1 bit to the
                                      # least-significant 0 bit available spot for it
            )
            \16
        )*
    )
)
\7                  # tail = the result of the move
\4                  # Assert that \4 is less than or equal to the result of the move
(
    .*$\3
|
    \4              # Double the value of \4 to compare against if \3 is non-empty,
                    # i.e. if we had an even number of total digits.
)

Galaretka , 6 bajtów

Bµċ0<S

Wypróbuj online!

J , 12 bajtów

(+/>-:@#)@#:

J wykonuje czasowniki od prawej do lewej, więc zacznijmy od końca i zmierzajmy do początku.

Wyjaśnienie

         #:       NB. Convert input to list of bits
       -:@#       NB. Half (-:) the (@) length (#)
          >       NB. Greater than 
         +/       NB. Sum (really plus (+) reduce (/)

Julia, 22 bajty

x->2*x<4^count_ones(x)

Oktawa , 26 bajtów

@(a)sum(2*dec2bin(a)-97)>0

Wypróbuj online!

PHP , 44 bajty

for(;$a=&$argn;$a>>=1)$r+=$a&1?:-1;echo$r>0;

Wypróbuj online!

PHP , 48 bajtów

<?=($c=count_chars(decbin($argn)))[49]-$c[48]>0;

Wypróbuj online!

Python 2 , 44 bajty

f=lambda n,c=0:f(n/2,c+n%2*2-1)if n else c>0

Wypróbuj online!

Stara odpowiedź, 47 bajtów

c,n=0,input()
while n:c+=n%2*2-1;n/=2
print c>0

Jest to po prostu port odpowiedzi na C w @ cleblanc . Jest dłuższy niż inne odpowiedzi w Pythonie, ale pomyślałem, że warto było to opublikować, ponieważ jest to zupełnie inna metoda znalezienia odpowiedzi.

Wypróbuj online!

C #, 82 bajty

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}