"En Bitti" Numarasını [kapalı] bulun

Dec 20 2020

Meydan okuma

Tam sayılar listesi verildiğinde, aralarındaki "bittiest" sayısı en fazla bit'e sahip olandır - yani 1'e ayarlanmış en büyük bit miktarıdır.

Giriş olarak 32 bitlik işaretli tam sayıların bir listesini alan ve bunların arasından "bittiest" sayısını çıktı olarak döndüren bir fonksiyon (veya program) yazın.

Listede en az bir öğe olduğunu varsayabilirsiniz.

Test Durumları

Giriş: 1, 2, 3, 4

Çıktı: 3

Giriş: 123, 64, 0, -4

Çıktı: -4

Giriş: 7, 11

Çıktı: Ya 7ya da 11(ikisi birden değil)

Giriş: 1073741824, 1073741823

Çıktı: 1073741823

İyi şanslar

Bu kod golf, yani bayt cinsinden en kısa program kazanır.

Açıklama

O tüm tamsayıları temsil edebilir sürece temsil: Dil 32 bitlik imzalı tamsayı desteklemiyorsa, başka sayısal (metinsel değil okuyun) kullanabilir -2^31için 2^31 - 1kullanarak, kapsayıcı ikinin tamamlayıcısı negatifleri için.

Yanıtlar

10 GioD Dec 21 2020 at 13:54

Jöle , 13 12 8 bayt

%Ø%B§µÞṪ

Çevrimiçi deneyin!

Açıklama

     µÞ  | sort input by
%Ø%      | modulo by 2^32 (Ø% is a quick for 2^32)
   B     | converted to binary
    §    | sum
       Ṫ | get the last

Düzenleme: İlk soruma verdiğiniz nazik yanıt için hepinize teşekkür ederim! Sanırım şimdi düzelttim, tüm test durumları için çalışıyor gibi görünüyor.

Orijinal kod

2*31
B%¢S€iṀị
26 CodyGray Dec 20 2020 at 18:26

x86 Makine Dili, 18 bayt

31 D2 AD F3 0F B8 F8 39 FA 77 03 87 FA 93 E2 F2 93 C3 

Yukarıdaki baytlar, esiregisterdaki dizinin adresini ve registerdaki dizideki elemanların sayısını kabul eden ve registerdaki dizideki ecx"bittiest" sayısını döndüren bir fonksiyonu tanımlar eax.

Bunun, ecxve esiyazmaçlarındaki bağımsız değişkenleri kabul eden özel bir arama kuralı olduğuna dikkat edin , ancak bunun dışında dizinin uzunluğunu ve diziye bir göstericiyi iki bağımsız değişken olarak alan bir C işlevine benzer. Bu özel arama kuralı, tüm kayıtları çağıran kaydetme olarak ele alır ebx.

Bu işlevin uygulanması, zorlamada belirtildiği gibi dizinin en az 1 öğeye sahip olduğunu varsayan bazı kirli hileler çeker. Ayrıca , bildiğim tüm arama kurallarında standart olan yön bayrağının ( DF) clear ( 0) olduğunu varsayar .

Kurtulmamış montaj dili anımsatıcılarında:

; ecx = length of array
; esi = address of first element in array
Find:
    31 D2          xor    edx, edx                ; start with max bit count set to 0
Next:
    AD             lods   eax, DWORD PTR [esi]    ; load the next value from the array, and
                                                  ;   increment ptr by element size
    F3 0F B8 F8    popcnt edi, eax                ; count # of set bits in value
    39 FA          cmp    edx, edi                ; if # of set bits in value is less than
    77 03          ja     SHORT Skip              ;   the running maximum, skip next 2 insns
    87 FA          xchg   edx, edi                ; save current # of set bits (for comparisons)
    93             xchg   eax, ebx                ; save current array value (for comparisons)
Skip:
    E2 F2          loop   SHORT Next              ; decrement element count, looping until it is 0
    93             xchg   eax, ebx                ; move running maximum value to eax
    C3             ret                            ; return, with result in eax

Bu kodun temel özelliği, elbette, popcntbir tamsayıdaki set bitlerinin sayısını sayan x86 komutudur. Girdi dizisi boyunca yineler, hem maksimum elemanın değerini hem de içerdiği küme bitlerinin sayısını takip eder. Dizideki her bir değeri, set bitlerinin sayısının daha önce gördüğü herhangi bir değerden daha yüksek olup olmadığını kontrol eder. Eğer öyleyse, izleme değerlerini günceller; değilse, bu adımı atlar.

popcntTalimat geniş (4 bayt) talimat, ama bu önlemek için yapılabilecek bir şey yok. Bununla birlikte, çok kısa (1 bayt) lodskomut, aynı anda işaretçiyi artırırken diziden değerleri yüklemek için kullanılmıştır, kısa (2 bayt) loopkomut döngü kontrolü için kullanılmıştır (öğe sayacını otomatik olarak azaltır ve uzun süre döngü yapar) çünkü geçecek daha fazla öğe kaldığından) ve baştan sona çok kısa (1 baytlık) xchgtalimat kullanılmıştır.

Her zaman sicile yüklenen talimatın xchgkullanılmasını sağlamak için sonunda fazladan bir şey kullanılması gerekiyordu , ancak bu takas buna değer.lodseax

Çevrimiçi deneyin!

İlk denemem 20 baytlık bir işlevdi. Şimdiye kadar, 18 bayt bulabildiğim en iyisi. Başka birinin bu skoru geçip geçemeyeceğini merak ediyorum!

Gördüğüm tek iyileştirme yolu, bir LOOPAtalimatın var olması olurdu . Ne yazık ki, gelmiyor.Fark okunur durum kodları tarafından desteklenen LOOPvardır E/ Zve NE/ NZ. Ama belki bir başkası fikrini benden daha fazla uzatabilir!

18 Arnauld Dec 20 2020 at 03:58

JavaScript (ES6),  49 48 47  45 bayt

@ User81655 sayesinde 2 bayt tasarruf edildi

a=>a.sort(g=(p,q)=>!p|-!q||g(p&p-1,q&q-1))[0]

Çevrimiçi deneyin!

Nasıl?

Bu .sort()giriş verilmiştir, bu yinelemeli fonksiyonlu listesi pve qbunlardan biri, 0 eşit olana kadar, her değişken en az önemli bit kümesi temizler (ya da aynı anda her ikisi). Bu, listeyi en çok bit kümesinden en az bit kümesine doğru sıralamayı sağlar. Daha sonra ilk girişi, yani "bittiest" olanı iade ederiz.

Yorum yaptı

a =>                 // a[] = input list
  a.sort(            // sort a[] ...
    g = (p, q) =>    // ... using the recursive function g:
      !p | -!q       //     -> +1 if p = 0 and q ≠ 0,
                     //     or -1 if q = 0,
      ||             //     or  0 if p ≠ 0 and q ≠ 0, in which case ...
        g(           //     ... we do a recursive call:
          p & p - 1, //       clear the least significant bit set in p
          q & q - 1  //       clear the least significant bit set in q
        )            //     end of recursive call
  )[0]               // end of sort(); return the first entry
9 KamilaSzewczyk Dec 20 2020 at 03:45

APL (Dyalog Unicode) , 15 bayt

Adam ve ngn sayesinde birçok bayt kurtardı.

{⊃⍒+⌿⍵⊤⍨32⍴2}⊃⊢

Çevrimiçi deneyin!

8 Noodle9 Dec 20 2020 at 09:07

C (gcc) , 80 77 bayt

Att !!! sayesinde 3 bayt tasarruf etti !

#define b __builtin_popcount(f(n,l
f(n,l)int*l;{n=--n?f(n,l+(b))<b+1)))):*l;}

Çevrimiçi deneyin!

7 Zaiborg Dec 21 2020 at 22:41

C ++ (GCC) , 145 141 140 135 134 133 130 128 116 bayt

145-> 141
tavan kedisi sayesinde 128-> 116 kullanıcı sayesinde

#import<bits/stdc++.h>
int i,b,v,c;main(){for(;std::cin>>i;b<c?b=c,v=i:0)c=std::bitset<32>(i).count();std::cout<<v;}

Çevrimiçi deneyin!

6 pavi2410 Dec 21 2020 at 23:13

Kotlin , 41 38 29 bayt

Çok daha az bayt içeren kodu düzeltin :) {Teşekkürler @vrintle}

{it.maxBy{it.countOneBits()}}

Kotlin Bahçesi


{it.maxBy{it.toByte().countOneBits()}}

Kotlin Bahçesi


{it.maxBy{it.toString(2).count{it=='1'}}}

Çevrimiçi deneyin!

6 Makonede Dec 21 2020 at 01:44

05AB1E , 9 bayt

ΣžJ%b1¢}θ

Çevrimiçi deneyin!

ΣžJ%b1¢}θ  # full program
        θ  # last element of...
           # implicit input...
Σ          # sorted in increasing order by...
      ¢    # number of...
     1     # ones...
      ¢    # in...
           # (implicit) current element in list...
   %       # modulo...
 žJ        # 4294967296...
    b      # in binary
           # implicit output
4 Giuseppe Dec 20 2020 at 05:32

R , 58 55 54 bayt

function(x)x[order(colSums(sapply(x,intToBits)<1))][1]

Çevrimiçi deneyin!

Robin Ryder'a -2 teşekkürler

- Dominic van Essen'e teşekkürler.

4 Razetime Dec 20 2020 at 10:30

Stax , 18 bayt

é·║⌂╞8Q⌡ë♀NM╟¥É▌╦!

Çalıştırın ve hatalarını ayıklayın

Doğru gösterimi elde etmek için manuel olarak 1s / 0s ile pedler.

Her test senaryosu için tek bir sayı görüntüler.

4 GalenIvanov Dec 21 2020 at 15:02

K (ngn / k) , 11 bayt

{*x@>+/2\x}

Çevrimiçi deneyin!

4 Danis Dec 20 2020 at 19:02

Python 3 , 52 bayt

lambda l:max(l,key=lambda n:bin(n%2**31).count("1"))

Çevrimiçi deneyin!

n%2**31- python'da tam sayılar sonsuz olduğundan, negatif sayıları değiştirmek zorundadır. örneğin -4olur2147483644

bin(...) - ikili biçime çevir

count("1") - birim sayısını say


Python 3 , 50 bayt

lambda n:n and n%2+z(n//b)
f=lambda l:max(l,key=z)

Çevrimiçi deneyin!

iki bayt daha kısadır, ancak negatif sayılarla çalışmaz

4 Gabber Dec 22 2020 at 00:56

Scala , 54 42 40 36 bayt

Caird coinheringaahing, didymus, user ve bazı ipuçları sayesinde bayt tasarrufu sağlandı

_.maxBy(_.toBinaryString.count(48<))

Çevrimiçi deneyin!

3 DominicvanEssen Dec 20 2020 at 15:17

Kabuk , 17 16 13 bayt

Düzenleme: Razetime sayesinde -1 bayt ve ardından Leo sayesinde -3 bayt

►(ΣḋΩ≥0+^32 2

Çevrimiçi deneyin!

Husk, doğal olarak keyfi kesinlikte tamsayılar kullanır ve bu nedenle, negatif 4 baytlık işaretli tam sayıları temsil etmek için 32 bitlik 2'nin tamamlayıcısı kavramına sahip değildir: sonuç olarak, 'ikili rakamları elde etme' işlevi - - burada ne yazık ki negatif girişler için yararsızdır.
Bu nedenle, '2'nin tamamlayıcı bittiliğini' elle hesaplamamız gerekir.

Buradaki kullanım için Leo'nun Husk yardımına teşekkürler .Ω

►                       # element of input that maximises result of:
 (Σḋ                    # sum of binary digits of
    Ω                   # repeat until result is
     ≥0                 # greater than or equal to zero:
       +^32 2           # add 2^32
3 KevinCruijssen Dec 21 2020 at 22:13

Java 10, 73 bayt

a->{int r=0,m=0,t;for(var i:a)if((t=i.bitCount(i))>m){m=t;r=i;}return r;}

Çevrimiçi deneyin.

Açıklama:

a->{                     // Method with Integer-array parameter and int return-type
  int r=0,               //  Result-integer, starting at 0
      m=0,               //  Maximum bit-count integer, starting at 0
      t;                 //  Temp integer, uninitialized
  for(var i:a)           //  Loop over each Integer in the input-array:
    if((t=i.bitCount(i)) //   If its amount of 1s in the binary representation
       >m){              //   is larger than the current maximum:
      m=t;               //    Update the maximum with this bit-count
      r=i;}              //    And update the result with this integer
  return r;}             //  After the loop, return the resulting integer
3 xigoi Dec 21 2020 at 20:53

Jöle , 9 8 bayt

%Ø%BSƲÞṪ

Çevrimiçi deneyin!

(Maksimum) Þyerine (sırala) kullanarak -1 bayt ÐṀ. Bu, Gio D'nin cevabından ilham aldı ve onların ve benim düzenlememden sonra, her iki çözüm de hemen hemen aynı.

Açıklama

%Ø%BSƲÞṪ   Main monadic link
      Þ    Sort by
     Ʋ     (
%            Modulo
 Ø%            2^32
   B         Binary
    S        Sum
     Ʋ     )
       Ṫ   Last item
3 Shaggy Dec 21 2020 at 17:11

Japt -h , 10 bayt

ñÈu2pH)¤¬x

Dene

ñÈu2pH)¤¬x     :Implicit input of array
ñ              :Sort by
 È             :Passing each element through the following function
  u            :Positive modulo
   2p          :  2 raised to the power of
     H         :  32
      )        :End modulo
       ¤       :To binary string
        ¬      :Split
         x     :Reduce by addition
               :Implicit output of last element
2 Xcali Dec 20 2020 at 06:47

Perl 5 , 54 bayt

sub f{(sprintf"%b",@_)=~y/1//}($_)=sort{f($b)<=>f$a}@F

Çevrimiçi deneyin!

2 vrintle Dec 20 2020 at 10:55

Ruby 2.7 , 36 33 34 bayt

Özel bir durum için kodumu düzelttiği için Dingus'a teşekkürler ! :)

p$*.max_by{("%034b"%_1)[2,32].sum}

Çevrimiçi deneyin!

Giriş için komut satırı argümanlarını kullanır, bittiest sayıyı string olarak çıkarır . TIO, Ruby'nin eski bir sürümünü kullanır, oysa Ruby 2.7'de, iki bayt tasarrufu sağlayan parametreleri numaralandırdık.

2 user Dec 21 2020 at 22:25

Java (JDK) , 44 bayt

a->a.max((x,y)->x.bitCount(x)-x.bitCount(y))

Çevrimiçi deneyin!

Bu bir tür aldatmadır, çünkü bir Stream<Integer>girdi olarak kabul eder ve bir Optional<Int>.

2 user Dec 22 2020 at 04:21

Scala , 24 bayt

_ maxBy Integer.bitCount

Çevrimiçi deneyin!

Gabber'in harika ilk cevabından ayrıldı .

2 didymus Dec 22 2020 at 03:29

C # (Visual C # Etkileşimli Derleyici) , 71 58 bayt

l=>l.OrderBy(r=>Convert.ToString(r,2).Sum(c=>c-48)).Last()

Çevrimiçi deneyin!

  • @User tarafından yorumlarda önerildiği gibi bir lambda kullanmak için yeniden düzenlendi
1 Neil Dec 20 2020 at 04:34

Kömür , 22 bayt

≔EθΣ⍘﹪ιX²¦³²¦²ηI§θ⌕η⌈η

Çevrimiçi deneyin! Bağlantı, kodun ayrıntılı sürümüne yöneliktir. Açıklama:

≔EθΣ⍘﹪ιX²¦³²¦²η

Listedeki her sayı için, onu 32 bitlik işaretsiz bir sayıya çevirin, ikiliye çevirin ve bitleri toplayın.

I§θ⌕η⌈η

En yüksek bit sayısı konumundaki sayıyı verir.

1 ChrisLoonam Dec 20 2020 at 13:14

SystemVerilog, 66 bayt

Telefonumdan yayınladığım için $countones()şimdilik mükemmel olmayan bir cevap olacak, ancak burada SV’nin işlevi mükemmel.

function m(int q[$]);
m=q.max with ($countones(item));
endfunction
1 att Dec 21 2020 at 04:29

Wolfram Dili (Mathematica) , 39 bayt

Last@*SortBy[Mod[#,2^32]~DigitCount~2&]

Çevrimiçi deneyin!

1 ZaelinGoodman Dec 21 2020 at 03:32

PowerShell, 53 56 bayt

Negatifleri düzgün işlemediği için +5 bayt
- mazzy sayesinde -2 bayt

$args|sort{$v=$_;0..31|%{$o+=!!(1-shl$_-band$v)};$o}-b 1
1 xigoi Dec 21 2020 at 21:20

Nim , 75 bayt

import algorithm,bitops
func b(n:seq):int=n.sortedByIt(it.countSetBits)[^1]

Çevrimiçi deneyin!

1 roblogic Dec 22 2020 at 05:17

Zsh, 85 bayt

çevrimiçi deneyin!

for i;{c=${#${(M)${(s::)$((i<0?[##2]2**32+i:[##2]i))}#1}}
((c>d))&&j=$i&&d=$c;}
<<<$j

Büyük meydan okuma, en tuhaf Zshbüyülerden bazılarını gerektiriyordu ! Açıklama:
for i;{... tüm argümanlar üzerinde örtülü yineleme
$((i<0?[##2]2**32+i:[##2]i))... dönüştürmek i32 bit formatına, eğer ikinin tamamlayıcısı hile kullanarak i<0
${#${(M)${(s::) //expression// }#1}}, diziye dize genişletmek (M) atch o elemanlarını saymak ... 1
((c>d))&&j=$i&&d=$c... rapor takibi hangi giriş iolduğunu sayıya göre "bittiest" c
<<<$j... kazanan çıktı

1 wroth Dec 22 2020 at 08:54

J , 20 bayt

{.@\:[:+/"1(32$2)&#:

Yazıldığı gibi, birden çok eşit, maksimum bitlik sayı verildiğinde, dizideki ilkini döndürür. Olarak {.\:değiştirilirse {:/:, sonuncuyu verir. Çevrimiçi deneyin!

1 EasyasPi Dec 23 2020 at 12:09

AArch64, 48 44 bayt

Ham talimatlar (32-bit küçük endian hex):

1e2703e4 bc404400 0e205801 2e303821
0ea43c23 2ea31c02 2ea31c24 f1000421
54ffff21 1e260040 d65f03c0

Yorumlanmamış montaj:

        .globl bittiest
bittiest:
        fmov    s4, #0
.Lloop:
        ldr     s0, [x0], #4
        cnt     v1.8b, v0.8b
        uaddlv  h1, v1.8b
        cmge    v3.2s, v1.2s, v4.2s
        bit     v2.8b, v0.8b, v3.8b
        bit     v4.8b, v1.8b, v3.8b
        subs    x1, x1, #1
        bne     .Lloop
        fmov    w0, s2
        ret

Açıklama

C işlev imzası:

int32_t bittiest(int32_t *words, size_t len);

Sözde-C:

int32_t bittiest(int32_t *words, size_t len)
{
    int32_t maxcount = 0;
    int32_t maxvalue;
    do {
        int32_t value = *words++;
        int8_t counts[4] = popcount8x4((int8_t *)&value);
        int32_t count = counts[0] + counts[1] + counts[2] + counts[3];
        if (count >= maxcount) {
            maxvalue = value;
            maxcount = count;
        }
    } while (--len);
    return maxvalue;
}

AArch64'ün popülasyon sayımı talimatı NEON (SIMD / kayan nokta komut seti) içindedir ve her baytı ayrı ayrı sayar. Bu nedenle, burada skalarlarla çalışmak biraz garip, bu yüzden her şeyi NEON'da yapıyoruz.

v4, maksimum popülasyon sayısıdır (v4, s4, h4 ve d4'ün tümü aynı kaydı ifade eder). 0 olarak ayarlayın.

        fmov    s4, #0

Sonraki int32 sözcüğünü v0'a yükleyin ve sözcükleri (x0) 4 artırın.

        ldr     s0, [x0], #4

V0'daki her baytın popülasyon sayısını v1'deki karşılık gelen bayta depolayın.

        cnt     v1.8b, v0.8b

Tam popülasyon sayısını elde etmek için v1'deki 8 bitlik şeritlerin tümünü toplayın ve v1'de yeniden depolayın.

        uaddlv  h1, v1.8b

Bu kelimenin nüfus sayısını maksimum ile karşılaştırın. Daha büyük veya eşitse, v3'ün tümü 1 bit olacaktır (doğru), aksi takdirde tümü 0 bit olacaktır (yanlış).

        cmge    v3.2s, v1.2s, v4.2s

V3 doğruysa, maksimum kelimeyi (v2) mevcut kelimeye ayarlayın. max ilk yinelemede başlatılmaz, ancak her zaman ayarlanacaktır çünkü popülasyon sayısı her zaman> = 0 olacaktır.

        bit     v2.8b, v0.8b, v3.8b

Aynı, ancak yeni maksimum nüfus sayısı için.

        bit     v4.8b, v1.8b, v3.8b

Len (x1) değerini azaltın ve sıfır değilse döngü yapın

        subs    x1, x1, #1
        bne     .Lloop

Döngünün sonu: Maksimum değeri bir NEON yazmacından dönüş yazmacına (w0) taşıyın ve geri dönün.

        fmov    w0, s2
        ret

11 talimat = 44 bayt