Czy liczba jest binarna?

58

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 więc wygrywa najmniej bajtów w każdym języku

Skidsdev
źródło
Co się stanie, jeśli mój język nie będzie w stanie obsłużyć ostatniego przypadku testowego, ponieważ wykracza poza granice liczby dodatniej?
musicman523,
1
@ musicman523 afaik Standardowe reguły we / wy mówią, że musisz akceptować tylko liczby reprezentowane przez format liczbowy Twojego języka. Pamiętaj, że „granie” przy użyciu czegoś takiego jak boolfuck jest uważane za standardową
lukę
Czy liczy się jakaś wartość prawda / fałsz, czy potrzebujemy dwóch odrębnych wartości?
Erik the Outgolfer
@EriktheOutgolfer dowolna wartość
Skidsdev
6
Aka A072600 , jeśli to pomaga komukolwiek.
dcsohl,

Odpowiedzi:

28

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.

ZH Liu
źródło
Miły. Doszedłem do tego, co oczywiste, popcntzanim przewinąłem w dół, aby spojrzeć na odpowiedzi, ale nie myślałem o lzcntzajmowaniu się tylko znaczącymi cyframi, jak wymaga tego pytanie.
Peter Cordes
Czy jest jakiś sposób na uzyskanie oszczędności netto z używania bsrzamiast lzcnt(aka rep bsr)? Musisz użyć subzamiast, leaponieważ daje to 32-lzcnt. (Lub pozostawia dst niezmodyfikowany dla src = 0, na wszystkich istniejących urządzeniach Intel i AMD. AMD nawet dokumentuje to zachowanie, ale Intel twierdzi, że jest niezdefiniowany ... W każdym razie OP powiedział pozytywnie , co wyklucza 0.)
Peter Cordes
1
Zdecydowanie myślałem tak samo jak @Peter, ponieważ wyzwanie wyraźnie ogranicza dane wejściowe do dodatnich liczb całkowitych. W rzeczywistości miałem rozwiązanie opracowane przy użyciu popcnti bsr, ale było 17 bajtów. Myślałem, że to całkiem nieźle w porównaniu z pierwszą odpowiedzią asm, którą zobaczyłem , ale ta sprytna leasztuczka nie pozwala na to. Patrzyłem również na porównywanie bsfi popcnt. Ale nie widzę żadnego sposobu na pokonanie tego rozwiązania, nawet biorąc pod uwagę 1 bajt, który można zaoszczędzić, upuszczając repprefiks.
Cody Gray
1
salcnie jest równoważny z setc al: ostatnie zestawy aldo 1 CF, jeśli zestaw, a nie 255
Ruslan
1
Rzeczywisty ekwiwalent salcto sbb al, al, ale można zaoszczędzić 1 bajt, aby go zakodować. Nawiasem mówiąc, jest to udokumentowane przez AMD i jest szeroko wspierane przez Intel, a mnemonik pochodzi nawet z mapy operacyjnej P6 Intela. Tak więc ten jest właściwie całkiem bezpieczny w użyciu. Również miłe ulepszenie tutaj, aby pomyśleć o użyciu tej instrukcji! Jest to w zasadzie to, co zrobił mój oryginalny szkic, z wyjątkiem tego, że (1) użyłem kodu x86-64, więc inckodowanie było dwa razy dłuższe i (2) nie myślałem salc, więc wykonałem tę samą pracę w dłuższa droga. Szkoda, że ​​mogę głosować tylko raz.
Cody Gray
17

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.
Dennis
źródło
Miły. Miałem Bo-S, ale nie mogłem znaleźć 1-bajtowego atomu, który zamieniłby pozytywne / nie-pozytywne w prawdę / fałsz ...
ETHproductions
Logiczne lub z -1, prawda?
Lynn,
@ Lynn Tak, rzeczywiście. Dzięki.
Dennis
1
4 bajty
caird coinheringaahing 12.12.17
@cairdcoinheringaahing Dzięki, ale Æṃwtedy nie istniało.
Dennis,
14

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!

Pręt
źródło
2
Czy wiodące 0 w zwrocie binpowoduje to rozwiązanie problemu?
Shadow
3
@shadow Nie ma problemu, ze względu na sposób maxdziałania. W przypadku remisu, max zwróci pierwszą wartość w iteracji, która ma maksymalną wartość. Ten kod wykorzystuje ten fakt, aby upewnić się, że 1 jest zwracane w przypadku remisu, co w rzeczywistości oznacza, że ​​jest ich więcej niż zera, ponieważ dodano dodatkowe zero bin. W rzeczywistości byłby niepoprawny, gdyby został napisany w ten sposób, gdyby nie dodatkowe zero.
FryAmTheEggman
@FryAmTheEggman dotyczy to również starej odpowiedzi, w której cmpzwroty 0są równe
Rod
11

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
Stewie Griffin
źródło
Czy zestaw narzędzi komunikacyjnych jest standardową częścią Octave, czy może bardziej przypomina bibliotekę w innych językach?
dcsohl
Jest to pakiet dostarczany z instalacją. W niektórych instalacjach musisz go konkretnie załadować, aw innych automatycznie. Jest to część standardu na Octave-Online.net, więc używam tego jako odniesienia. (Kod musi działać w co najmniej jednym tłumaczu, który istniał przed wyzwaniem).
Stewie Griffin,
9

JavaScript (ES6), 36 34 bajtów

f=(n,x=0)=>n?f(n>>>1,x+n%2-.5):x>0
ETHprodukcje
źródło
f=(n,x=0)=>n?f(n>>>1,x+=n%2-.5):x>0dla 35 bajtów.
ovs
Użyj n>>1zamiast, n>>>1aby zapisać bajt, ponieważ dane wejściowe nigdy nie są ujemne.
kamoroso94,
@ kamoroso94 Dzięki, ale wtedy to się nie powiedzie 2147483648.
ETHproductions
@ETHproductions Darn, i n/2|0nie ma nic lepszego: /
kamoroso94,
8

Mathematica, 22 bajty

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

#>#2&@@#~DigitCount~2&
alephalpha
źródło
2
Myślę, że notacja infix ma wyższy priorytet niż @@.
Martin Ender
1
-1 bajt (jak zauważył @MartinEnder):#>#2&@@#~DigitCount~2&
JungHwan Min
7

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 .

Fatalizować
źródło
7

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

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

Wypróbuj online!

wrymug
źródło
5
Przekreślone 44 to wciąż 44
JungHwan Min
6

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!

cleblanc
źródło
Na podstawie wyjaśnienia OP możesz usunąćunsigned
musicman523,
Ponieważ nnn ma wartość dodatnią, możesz zmienić n>>=1na n/=2. Myślę też, że możesz użyć ~nzamiast tego n^-1, co powinno również pozwolić ci się zmienić &&na&
musicman523,
Dziwne rzeczy dzieją się, gdy edytuję komentarze - „nnn” oznacza n, nie mówiąc już o zmianie &&na &, nie sądzę, żeby to zadziałało. Ale zmiana *wydaje się działać
musicman523,
@ musicman523 &&Miałem tylko obsłużyć przypadek bez znaku, ale ponieważ potrzebuję tylko dodatnich liczb całkowitych, mogę to wszystko usunąć razem. Dobry pomysł na /=bycie krótszym, >>=ale dzięki!
cleblanc
Możesz zapisać jeden bajt zmieniając n&1?++i:--1na i+=n%2*2-1. Możesz się także pozbyć >0, stwierdzając, że wyślesz zero dla ciężkich i niezerowych dla nie ciężkich
musicman523,
6

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!

Giuseppe
źródło
Zobaczyłem twoją odpowiedź dopiero po wysłaniu mojego ... W każdym razie możesz użyć log2(n)zamiast log(n,2)zaoszczędzić 1 bajt
Maxim Mikhaylov
@MaxLawnboy ah, oczywiście. Dzięki!
Giuseppe,
Grał w golfa poza kolejnymi 12 bajtami: codegolf.stackexchange.com/a/132396/59530
JAD
6

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!

ბიმო
źródło
Czy jest jakiś konkretny powód, dla którego używasz 8d 1fzamiast 89 fb?
Ruslan,
2
Prawdziwe pytanie brzmi: czy istnieje jakiś szczególny powód, dla którego używasz tej obrzydliwej składni AT&T?!? Ponadto zarówno demontaż, jak i demontaż zgadzają się, że masz add eax, 2+ dec eax, ale twoje komentarze sugerują, że chcesz zwiększyć ebx, a nie eax.
Cody Gray
1
Możesz zamienić jnz Next/ add/ dec(7 bajtów) na lea -1(%rax, %rbx, 2), %eax(4 bajty) do zrobienia eax += 2*ebx - 1(jak w innej odpowiedzi kodu maszynowego x86 ). Następnie poza pętlą neg %eax(2 bajty) przed przesunięciem bitu znaku na dół. Oszczędność netto 1 bajta. Lub test %eax,%eax/ setge %aldziałałby również, jeśli twoją wartością zwracaną jest a boollub int8_t.
Peter Cordes
1
@PeterCordes Wydaje mi się, że wiem, co się stało, ale nie jestem pewien: mogłem nie spróbować, lea -1(%rax,rbx,2)ale lea -1(%eax,%eax,2)zmarnowałem bajty w ten sposób. W każdym razie oboje mieliście rację, mogę zapisać taki bajt. Wielkie dzięki (w zamian zmienię to leana movchwilę).
ბიმო
1
@ moonheart08: Wtedy nie wiedziałem o tym, ale ktoś opublikował odpowiedź, która pozwoliła zaoszczędzić 7 bajtów.
ბიმო
5

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)
}
Brad Gilbert b2gills
źródło
5

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
Kreator pszenicy
źródło
5

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!

nimi
źródło
mod n 2może być sprawiedliwy n, a bajt jest krótszy bez akumulatora. Wypróbuj online!
Ørjan Johansen
5

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.

Neil
źródło
${1}może być $+. Lub możesz użyć !zamiast, 0a następnie skrócić 01|10do .\b..
Martin Ender
@MartinEnder Huh, czy $+robi dobrą rzecz, gdy wzór zawiera znak |? Zastanawiam się, czy mógłbym użyć tego wcześniej ...
Neil
2
nie, $+jest super głupi i po prostu używa grupy z największą liczbą, bez względu na to, czy została użyta, czy nie. Przydaje się to do gry w golfa, gdy masz więcej niż dziewięć grup lub w sytuacji takiej jak ta tutaj, i nie wiem, dlaczego kiedykolwiek używałbym go w regexie produkcyjnym.
Martin Ender
5

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
MickyT
źródło
+1 zgrabne rozwiązanie! Nawet nie wiedziałem ointToBits
Giuseppe,
Grał w golfa na kolejne 4 bajty: codegolf.stackexchange.com/a/132396/59530
JAD
5

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:

F. George
źródło
4

Pyth, 9 7 bajtów

ehc2S.B

Wypróbuj tutaj.

-2 dzięki FryAmTheEggman .

Erik the Outgolfer
źródło
Kolejne podejście 9-bajtowe:>ysJjQ2lJ
KarlKastor
1
7 bajtów, ale wydaje mi się, że powinno być jeszcze coś krótszego ...
FryAmTheEggman
@FryAmTheEggman Hmm ... to może działać tylko jako pełny program. (Wiedziałem, że jest sposób na wykorzystanie .B!)
Erik Outgolfer
4

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.

JAD
źródło
4

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!

Destroigo
źródło
4

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:

111100101ones>zeroes1

ones>zeroesones1>zeroes1

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.
Ponury
źródło
2
Chociaż jest to inspirowane odpowiedzią Deadcode , algorytm jest na tyle inny, że czułem, że zasługuje na osobną odpowiedź, a nie komentarz.
Grimmy,
2
Jest to fenomenalne i dokładnie to, co chciałem zobaczyć (ktoś wydmuchuje moje wyrażenie regularne z wody za pomocą bardziej zwięzłego algorytmu). Ale twoje komentarze tak naprawdę wcale tego nie wyjaśniają, a skomentowana 73-bajtowa wersja wyrażenia regularnego nawet nie działa (wsteczne odnośniki \5są wyłączone o jeden). Przestudiowałem to, wyjaśniłem i skomentowałem w mojej odpowiedzi (ponieważ StackExchange nie zezwala na odpowiedzi wielowierszowe).
Deadcode
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.
)
Deadcode
źródło
1
-98 bajtów
Grimmy
3

Galaretka , 6 bajtów

Bµċ0<S

Wypróbuj online!

Erik the Outgolfer
źródło
Bo-Smożna użyć do obliczenia binarnej „wagi” danych wejściowych, niestety najkrótszym sposobem, który wydaje się być Bo-S>0
ETHproductions
@ETHproductions Tak, jeszcze nie ma atomu „pozytywnego”.
Erik the Outgolfer,
Najwyraźniej działa: P
ETHprodukcje
3

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 (/)
Dan Bron
źródło
1
(#<2*+/)@#:powinienem uratować 1, chyba że coś mi umknie.
FrownyFrog,
3

Julia, 22 bajty

x->2*x<4^count_ones(x)
Tanj
źródło
2

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!

musicman523
źródło
2

C #, 82 bajty

n=>{var s=System.Convert.ToString(n,2);return s.Replace("0","").Length>s.Length/2}
TheLethalCoder
źródło
Możesz przyciąć jeszcze więcej, traktując ciąg jako IEnumerable <char>. n=>{var s=Convert.ToString(n,2);return s.Count(c=>c=='1')>s.Length/2;}
GalacticCowboy
@GalacticCowboy To dodaje 11 bajtów, ponieważ musisz w pełni się zakwalifikować Converti dołączyć using System.Linq;(napisane krótszy jako namespace System.Linq{}). Fajny pomysł po prostu nie goli się wystarczająco, aby uzasadnić oszczędność w tym przypadku.
TheLethalCoder