"En Bitti" Numarasını [kapalı] bulun
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 7
ya 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^31
için 2^31 - 1
kullanarak, kapsayıcı ikinin tamamlayıcısı negatifleri için.
Yanıtlar
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Ṁị
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, esi
registerdaki 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, ecx
ve esi
yazmaç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, popcnt
bir 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.
popcnt
Talimat geniş (4 bayt) talimat, ama bu önlemek için yapılabilecek bir şey yok. Bununla birlikte, çok kısa (1 bayt) lods
komut, aynı anda işaretçiyi artırırken diziden değerleri yüklemek için kullanılmıştır, kısa (2 bayt) loop
komut 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) xchg
talimat kullanılmıştır.
Her zaman sicile yüklenen talimatın xchg
kullanılmasını sağlamak için sonunda fazladan bir şey kullanılması gerekiyordu , ancak bu takas buna değer.lods
eax
Ç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 LOOPA
talimatın var olması olurdu . Ne yazık ki, gelmiyor.Fark okunur durum kodları tarafından desteklenen LOOP
vardır E
/ Z
ve NE
/ NZ
. Ama belki bir başkası fikrini benden daha fazla uzatabilir!
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 p
ve q
bunlardan 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
APL (Dyalog Unicode) , 15 bayt
Adam ve ngn sayesinde birçok bayt kurtardı.
{⊃⍒+⌿⍵⊤⍨32⍴2}⊃⊢
Çevrimiçi deneyin!
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!
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!
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!
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
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.
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.
K (ngn / k) , 11 bayt
{*x@>+/2\x}
Çevrimiçi deneyin!
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 -4
olur2147483644
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
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!
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
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
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
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
Perl 5 , 54 bayt
sub f{(sprintf"%b",@_)=~y/1//}($_)=sort{f($b)<=>f$a}@F
Çevrimiçi deneyin!
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.
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>
.
Scala , 24 bayt
_ maxBy Integer.bitCount
Çevrimiçi deneyin!
Gabber'in harika ilk cevabından ayrıldı .
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
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.
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
Wolfram Dili (Mathematica) , 39 bayt
Last@*SortBy[Mod[#,2^32]~DigitCount~2&]
Çevrimiçi deneyin!
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
Nim , 75 bayt
import algorithm,bitops
func b(n:seq):int=n.sortedByIt(it.countSetBits)[^1]
Çevrimiçi deneyin!
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 Zsh
bü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 i
32 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ş i
olduğunu sayıya göre "bittiest" c
<<<$j
... kazanan çıktı
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!
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