「Bittiest」番号を見つける[クローズ]

Dec 20 2020

チャレンジ

整数のリストが与えられると、それらの中で「最もビットの多い」数は、最も多くのビットがオンになっている数です。つまり、最大のビット数が1に設定されます。

32ビットの符号付き整数のリストを入力として受け取り、その中で「最もビットの多い」数値を出力として返す関数(またはプログラム)を記述します。

リストには少なくとも1つの項目があると想定できます。

テストケース

入力: 1, 2, 3, 4

出力: 3

入力: 123, 64, 0, -4

出力: -4

入力: 7, 11

出力:いずれか7または11(両方ではない)

入力: 1073741824, 1073741823

出力: 1073741823

がんばろう

これはコードゴルフなので、バイト単位の最短プログラムが優先されます。

明確化

言語が32ビットの符号付き整数をサポートしていない場合は、負の値に2の補数を使用して、から-2^312^31 - 1含むすべての整数を表すことができる限り、他の数値(読み取り:テキストではない)表現を使用できます。

回答

10 GioD Dec 21 2020 at 13:54

ゼリー、13の 12 8バイト

%Ø%B§µÞṪ

オンラインでお試しください!

説明

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

編集:私の最初の質問への親切な回答に感謝します!私は今それを修正したと思います、それはすべてのテストケースで機能するようです。

元のコード

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

x86機械語、18バイト

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

上記のバイトは、esiレジスタ内の配列のアドレスとレジスタ内の配列内の要素の数を受け入れ、レジスタ内の配列内ecxの「最もビットの多い」数を返す関数を定義しますeax

これは、ecxおよびesiレジスタ内の引数を受け入れるカスタム呼び出し規約ですが、それ以外の点では、配列の長さと配列へのポインタを2つの引数として受け取るC関数によく似ています。このカスタム呼び出し規約は、を含むすべてのレジスタを呼び出し元保存として扱いますebx

この関数の実装は、チャレンジで提供されているように、配列に少なくとも1つの要素があることを前提とするいくつかの汚いトリックを引き出します。また、方向フラグ(DF)がクリア(0)であると想定しています。これは、私が知っているすべての呼び出し規約の標準です。

ゴルフを使わないアセンブリ言語ニーモニックでは:

; 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

このコードの重要な機能は、もちろん、popcnt整数のセットビット数をカウントするx86命令です。最大要素の値とそれに含まれるセットビット数の両方を追跡しながら、入力配列を反復処理します。配列内の各値をチェックして、設定されたビット数が以前に確認した値よりも多いかどうかを確認します。その場合、追跡値を更新します。そうでない場合は、このステップをスキップします。

popcnt命令は、大規模な(4バイト)の命令であるが、それを避けるために行うことができることは何もありません。ただし、非常に短い(1バイト)lods命令は、ポインターを同時にインクリメントしながら配列から値をロードするために使用され、短い(2バイト)loop命令は、ループ制御(要素カウンターを自動的にデクリメントし、長い間ループする)に使用されています。通過する要素が残っているため)、非常に短い(1バイト)xchg命令が全体で使用されています。

常にレジスタにロードされる命令をxchg使用できるようにするために、最後にエクストラを使用する必要がありましたが、そのトレードオフはそれ以上の価値があります。lodseax

オンラインでお試しください!

私の最初の試みは20バイトの関数でした。これまでのところ、18バイトは私が思いついた中で最高です。他の誰かがこのスコアを打ち負かすことができるかどうか知りたいです!

私が見る唯一の改善の道は、LOOPA命令が存在するかどうかです。残念ながら、そうではありません。サポートされてLOOPいる条件コードはE/ZNE/だけNZです。しかし、誰か他の人が私よりもさらに心を伸ばすことができるかもしれません!

18 Arnauld Dec 20 2020 at 03:58

JavaScript(ES6)、 49 48  4745バイト

@ user81655のおかげで2バイト節約できました

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

オンラインでお試しください!

どうやって?

.sort()再帰関数を使用して入力リストを作成します。この関数を指定するpq、各変数に設定されている最下位ビットが、一方が0になるまで(または両方が同時に)クリアされます。これにより、リストを最も多いビットから最も少ないビットのセットに並べ替えることができます。次に、最初のエントリ、つまり「最もビットの多い」エントリを返します。

コメント

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バイト

Adamとngnのおかげで多くのバイトを節約できました。

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

オンラインでお試しください!

8 Noodle9 Dec 20 2020 at 09:07

C(GCC) 、80の77バイト

attのおかげで3バイト節約できました!!!

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

オンラインでお試しください!

7 Zaiborg Dec 21 2020 at 22:41

C ++(GCC) 、145 141 140 135 134 133 130 128 116バイト

145-> 141ユーザーの
おかげで128-> 116天井猫のおかげで

#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;}

オンラインでお試しください!

6 pavi2410 Dec 21 2020 at 23:13

Kotlin、41の 38 29バイト

はるかに少ないバイトで正しいコード:){ありがとう@vrintle}

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

コトリンプレイグラウンド


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

コトリンプレイグラウンド


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

オンラインでお試しください!

6 Makonede Dec 21 2020 at 01:44

05AB1E、9バイト

ΣžJ%b1¢}θ

オンラインでお試しください!

Σž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バイト

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

オンラインでお試しください!

-ロビンライダーのおかげで2

-Dominic vanEssenに感謝します。

4 Razetime Dec 20 2020 at 10:30

Stax、18バイト

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

実行してデバッグする

正しい表現を得るために、手動で1/0を埋め込みます。

テストケースごとに1つの番号を表示します。

4 GalenIvanov Dec 21 2020 at 15:02

K(ngn / k)、11バイト

{*x@>+/2\x}

オンラインでお試しください!

4 Danis Dec 20 2020 at 19:02

Python 3、52バイト

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

オンラインでお試しください!

n%2**31--Pythonでは整数は無限大なので、負の数を変更する必要があります。たとえば-4なりました2147483644

bin(...) -バイナリ形式に変換します

count("1") -ユニットの数を数える


Python 3、50バイト

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

オンラインでお試しください!

2バイト短いが、負の数では機能しない

4 Gabber Dec 22 2020 at 00:56

スカラ、 54の 42 40 36バイト

caird coinheringaahing、didymus、ユーザー、およびいくつかのヒントのおかげで、いくつかのバイトを節約しました

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

オンラインでお試しください!

3 DominicvanEssen Dec 20 2020 at 15:17

殻、17の 16 13バイト

編集:Razetimeのおかげで-1バイト、次にLeoのおかげで-3バイト

►(ΣḋΩ≥0+^32 2

オンラインでお試しください!

Huskはネイティブに任意精度の整数を使用するため、負の4バイト符号付き整数を表すための32ビット2の補数の概念はありません。その結果、「バイナリ桁を取得」関数は、ここでは負の入力には使用できません。
したがって、「2の補数の苦味」を手動で計算する必要があります。

ここを使用してくれたLeoのHuskの助けに感謝します。Ω

►                       # 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バイト

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

オンラインでお試しください。

説明:

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

ゼリー、 9つの 8バイト

%Ø%BSƲÞṪ

オンラインでお試しください!

- (最大)のÞ代わりにÐṀ(ソート)を使用して1バイト。これはGioDの回答に触発され、彼らと私の編集の後、両方のソリューションはほとんど同じです。

説明

%Ø%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バイト

ñÈu2pH)¤¬x

それを試してみてください

ñÈ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バイト

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

オンラインでお試しください!

2 vrintle Dec 20 2020 at 10:55

ルビー2.7、36の 33 34バイト

特別な場合のために私のコードを修正してくれたDingusに感謝します!:)

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

オンラインでお試しください!

入力にコマンドライン引数を使用し、最も小さい数値を文字列として出力します。TIOは古いバージョンのRubyを使用しますが、Ruby 2.7では、2バイトを節約するパラメーターに番号を付けました。

2 user Dec 21 2020 at 22:25

Java(JDK)、44バイト

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

オンラインでお試しください!

これは一種の不正行為です。Stream<Integer>入力としてを受け入れ、を返しますOptional<Int>

2 user Dec 22 2020 at 04:21

Scala、24バイト

_ maxBy Integer.bitCount

オンラインでお試しください!

Gabberの素晴らしい最初の答えから切り離してください。

2 didymus Dec 22 2020 at 03:29

C#(Visual C#インタラクティブコンパイラ)、7158バイト

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

オンラインでお試しください!

  • コメントで@userによって提案されたラムダを使用するようにリファクタリングされました
1 Neil Dec 20 2020 at 04:34

チャコール、22バイト

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

オンラインでお試しください!リンクは、コードの詳細バージョンへのリンクです。説明:

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

リスト内の数値ごとに、32ビットの符号なし数値にキャストし、2進数に変換して、ビットを合計します。

I§θ⌕η⌈η

ビット数が最も多い位置の数値を出力します。

1 ChrisLoonam Dec 20 2020 at 13:14

SystemVerilog、66バイト

私は自分の携帯電話から投稿しているので、これは今のところ不完全な答えになりますが、SVの$countones()機能はここでは完璧です。

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

Wolfram言語(Mathematica)、39バイト

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

オンラインでお試しください!

1 ZaelinGoodman Dec 21 2020 at 03:32

PowerShellの、 53の 56バイト

ネガを適切に処理しなかったため+5バイト
mazzyのおかげで-2バイト

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

Nim、75バイト

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

オンラインでお試しください!

1 roblogic Dec 22 2020 at 05:17

Zsh、85バイト

オンラインでお試しください!

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

大きな挑戦、最も奇妙なZsh呪文のいくつかが必要でした!説明:
for i;{...すべての引数に対する暗黙の反復
$((i<0?[##2]2**32+i:[##2]i))... i2の補数のトリックを使用して32ビット形式に変換します...i<0
${#${(M)${(s::) //expression// }#1}}文字列を配列に展開し、(M)atchする要素をカウントします1
((c>d))&&j=$i&&d=$c...どの入力iがであるかを追跡しますカウントによると「最も小さい」c
<<<$j...勝者を出力する

1 wroth Dec 22 2020 at 08:54

J、20バイト

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

書かれているように、複数の等しく、最大にビット数が与えられると、配列の最初のものを返します。に{.\:変更する{:/:と、最後になります。オンラインでお試しください!

1 EasyasPi Dec 23 2020 at 12:09

AArch64、 48の 44バイト

生の命令(32ビットリトルエンディアン16進数):

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

コメントなしのアセンブリ:

        .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

説明

C関数のシグネチャ:

int32_t bittiest(int32_t *words, size_t len);

疑似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のポピュレーションカウント命令はNEON(SIMD /浮動小数点命令セット)にあり、各バイトを個別にカウントします。したがって、ここでスカラーを操作するのは少し厄介なので、すべてをNEONで実行します。

v4は最大人口数です(v4、s4、h4、およびd4はすべて同じレジスターを参照します)。0に設定します。

        fmov    s4, #0

次のint32ワードをv0にロードし、ワード(x0)を4インクリメントします。

        ldr     s0, [x0], #4

v0の各バイトのポピュレーションカウントをv1の対応するバイトに格納します。

        cnt     v1.8b, v0.8b

v1のすべての8ビットレーンを合計して完全な母集団カウントを取得し、v1に再度格納します。

        uaddlv  h1, v1.8b

この単語の人口数を最大値と比較します。それ以上の場合、v3はすべて1ビット(true)になり、そうでない場合はすべて0ビット(false)になります。

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

v3がtrueの場合、最大ワード(v2)を現在のワードに設定します。maxは最初の反復では初期化されませんが、人口数は常に> = 0であるため、常に設定されます。

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

同じですが、新しい最大人口数についてです。

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

len(x1)をデクリメントし、ゼロでない場合はループします

        subs    x1, x1, #1
        bne     .Lloop

ループ終了:最大値をNEONレジスタからリターンレジスタ(w0)に移動して戻ります。

        fmov    w0, s2
        ret

11命令= 44バイト