"가장 좋은"번호 찾기 [닫힘]

Dec 20 2020

도전

정수 목록이 주어지면 그중 "가장 작은"숫자는 가장 많은 비트가있는 숫자입니다. 즉, 가장 많은 비트가 1로 설정됩니다.

32 비트 부호있는 정수 목록을 입력으로 취하고 그 중에서 "가장 작은"숫자를 출력으로 반환하는 함수 (또는 프로그램)를 작성합니다.

목록에 하나 이상의 항목이 있다고 가정 할 수 있습니다.

테스트 케이스

입력: 1, 2, 3, 4

산출: 3

입력: 123, 64, 0, -4

산출: -4

입력: 7, 11

출력 : 7또는 11(둘다는 아님)

입력: 1073741824, 1073741823

산출: 1073741823

행운을 빕니다

이것은 코드 골프이므로 바이트 단위의 가장 짧은 프로그램이 이깁니다.

설명

이 모든 정수를 나타낼 수있는만큼 표현 : 언어는 부호있는 32 비트 정수를 지원하지 않는 경우 다른 숫자를 (텍스트하지 읽기) 사용할 수 있습니다 -2^312^31 - 1사용 (포함) 2의 보수를 제외합니다.

답변

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있는 "bittiest"숫자를 반환 하는 함수를 정의합니다 eax.

이것은 ecxesi레지스터 에서 인수를 받아들이는 사용자 지정 호출 규칙 이지만 그렇지 않으면 배열의 길이와 배열에 대한 포인터를 두 인수로 취하는 C 함수와 매우 유사합니다. 이 사용자 지정 호출 규칙은를 포함하여 모든 레지스터를 호출자 저장으로 처리합니다 ebx.

이 함수의 구현은 챌린지에 제공된대로 배열에 최소 1 개의 요소가 있다고 가정하는 더러운 트릭을 가져옵니다. 또한 방향 플래그 ( DF)가 명확 하다고 가정합니다 ( 0). 이것은 내가 알고있는 모든 호출 규칙에서 표준입니다.

ungolfed 어셈블리 언어 니모닉에서 :

; 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명령어는 배열에서 값을로드하는 동시에 포인터를 증가시키는 loop데 사용되었으며 , 짧은 (2 바이트) 명령어는 루프 제어에 사용되었습니다 (요소 카운터를 자동으로 감소시키고 길게 반복). 더 많은 요소가 남아 있으므로), 매우 짧은 (1 바이트) xchg명령어가 전체적으로 사용되었습니다.

레지스터에 항상 로드 되는 명령어 xchg를 사용하려면 마지막에 추가 를 사용해야 했지만 그 절충은 그만한 가치가 있습니다.lodseax

온라인으로 시도하십시오!

내 첫 번째 시도는 20 바이트 함수였습니다. 지금까지 18 바이트가 제가 생각 해낼 수있는 최고입니다. 다른 사람이이 점수를 이길 수 있는지 궁금합니다!

내가 보는 유일한 개선 경로는 LOOPA지침이 존재 하는 경우 입니다. 불행히도 그렇지 않습니다.에서 지원하는 유일한 조건 코드 LOOPE/ ZNE/ NZ입니다. 하지만 다른 사람이 나보다 마음을 더 넓힐 수 있습니다!

18 Arnauld Dec 20 2020 at 03:58

JavaScript (ES6),  49 48 47  45 바이트

@ user81655 덕분에 2 바이트 절약

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

온라인으로 시도하십시오!

어떻게?

우리 .sort()는 재귀 함수가있는 입력 목록입니다. p그리고 주어진 q변수 중 하나가 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 ceilingcat 덕분에

#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()}}

Kotlin 플레이 그라운드


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

Kotlin 플레이 그라운드


{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 Robin Ryder 덕분에

-1 Dominic van Essen 덕분입니다.

4 Razetime Dec 20 2020 at 10:30

Stax , 18 바이트

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

실행 및 디버그

올바른 표현을 얻기 위해 1s / 0s로 수동으로 채 웁니다.

각 테스트 케이스에 대해 단일 숫자를 표시합니다.

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-파이썬에서 정수는 무한하므로 음수를 변경해야합니다. 예가 -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

Scala , 54 42 40 36 바이트

caird coinheringaahing, didymus, user 및 몇 가지 팁 덕분에 일부 바이트를 절약했습니다.

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

온라인으로 시도하십시오!

3 DominicvanEssen Dec 20 2020 at 15:17

Husk , 17 16 13 바이트

편집 : Razetime 덕분에 -1 바이트, Leo 덕분에 -3 바이트

►(ΣḋΩ≥0+^32 2

온라인으로 시도하십시오!

Husk는 기본적으로 임의의 정밀도 정수를 사용하므로 음의 4 바이트 부호있는 정수를 나타내는 데 32 비트 2의 보수 개념이 없습니다. 결과적으로 '이진 숫자 가져 오기'함수 는 여기서 음수 입력에 쓸모가 없습니다.
그래서 우리는 '2의 보수 bittiness'를 손으로 계산해야합니다.

덕분에 껍질의 도움 레오 의 사용에 대한 Ω여기.

►                       # 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

자바 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ƲÞṪ

온라인으로 시도하십시오!

(maximum) Þ대신 (sort)를 사용하여 -1 바이트 ÐṀ. 이것은 Gio D의 답변에서 영감을 얻었으며 두 솔루션 모두 거의 동일합니다.

설명

%Ø%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

자바 (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 # 대화 형 컴파일러) , 71 58 바이트

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 비트 부호없는 숫자로 캐스트하고 이진수로 변환 한 다음 비트를 더합니다.

I§θ⌕η⌈η

가장 높은 비트 수의 위치에 숫자를 출력합니다.

1 ChrisLoonam Dec 20 2020 at 13:14

SystemVerilog, 66 바이트

지금은 내 폰에서 글을 올릴 때 불완전한 답 이겠지만 $countones()여기 SV의 기능은 완벽하다.

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))... i32 비트 형식으로 변환 , 경우 2의 보수 트릭을 사용하여 i<0
${#${(M)${(s::) //expression// }#1}}... 문자열을 배열로 확장하고 요소를 계산합니다. (M) atch 1
((c>d))&&j=$i&&d=$c... 어떤 입력 i이 입력되었는지 추적 카운트에 따라 "bittiest" 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이 참이면 최대 단어 (v2)를 현재 단어로 설정합니다. max는 첫 번째 반복에서 초기화되지 않지만 모집단 수가 항상> = 0이기 때문에 항상 설정됩니다.

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

동일하지만 새로운 최대 인구 수입니다.

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

len (x1)을 줄이고 0이 아닌 경우 루프

        subs    x1, x1, #1
        bne     .Lloop

루프 끝 : NEON 레지스터의 최대 값을 반환 레지스터 (w0)로 이동하고 반환합니다.

        fmov    w0, s2
        ret

11 개의 명령어 = 44 바이트