Tìm số "Bittiest" [đã đóng]

Question

Các thách thức

Đưa ra một danh sách các số nguyên, số "bittiest" trong số đó là số có nhiều bit nhất - tức là số bit lớn nhất được đặt thành 1.

Viết một hàm (hoặc một chương trình) nhận làm đầu vào một danh sách các số nguyên có dấu 32 bit và trả về đầu ra là số "bittiest" trong số đó.

Bạn có thể cho rằng danh sách có ít nhất một mục.

Các trường hợp kiểm tra

Đầu vào: 1, 2, 3, 4

Đầu ra: 3

Đầu vào: 123, 64, 0, -4

Đầu ra: -4

Đầu vào: 7, 11

Đầu ra: Một trong hai 7hoặc 11(nhưng không phải cả hai)

Đầu vào: 1073741824, 1073741823

Đầu ra: 1073741823

Chúc may mắn

Đây là chơi gôn mã, vì vậy chương trình ngắn nhất tính bằng byte sẽ thắng.

Làm rõ

Nếu ngôn ngữ của bạn không hỗ trợ số nguyên có dấu 32 bit, bạn có thể sử dụng bất kỳ biểu diễn số nào khác (đọc: không phải dạng văn bản) miễn là nó có thể đại diện cho tất cả các số nguyên từ bao gồm -2^31đến 2^31 - 1bao gồm, sử dụng phần bổ sung của hai cho phủ định.

Answer 1

Thạch , 13 12 8 byte

%Ø%B§µÞṪ

Hãy thử nó trực tuyến!

Giải trình

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

Chỉnh sửa: cảm ơn tất cả các bạn đã trả lời tốt cho câu hỏi đầu tiên của tôi! Tôi nghĩ rằng tôi đã sửa nó ngay bây giờ, nó dường như hoạt động cho tất cả các trường hợp thử nghiệm.

Mã gốc

2*31
B%¢S€iṀị

Answer 2

Ngôn ngữ máy x86, 18 byte

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

Các byte trên định nghĩa một hàm chấp nhận địa chỉ của mảng trong thanh esighi và số phần tử của mảng trong thanh ecxghi, và trả về số "bittiest" trong mảng trong thanh eaxghi.

Lưu ý rằng đây là một quy ước gọi tùy chỉnh chấp nhận các đối số trong ecxvà esiđăng ký, nhưng nó giống như một hàm C lấy độ dài của mảng và một con trỏ đến mảng làm hai đối số của nó. Quy ước gọi tùy chỉnh này coi tất cả các đăng ký là lưu người gọi, bao gồm cả ebx.

Việc triển khai hàm này kéo theo một số thủ thuật bẩn, giả sử rằng mảng có ít nhất 1 phần tử, như được cung cấp trong thử thách. Nó cũng giả định rằng cờ hướng ( DF) là clear ( 0), là tiêu chuẩn trong tất cả các quy ước gọi mà tôi biết.

Trong ghi nhớ của ngôn ngữ hợp ngữ không có cấu trúc:

; 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

Đặc điểm chính của mã này tất nhiên là lệnh x86 popcnt, đếm số bit đã đặt trong một số nguyên. Nó lặp lại qua mảng đầu vào, theo dõi cả giá trị của phần tử lớn nhất và số lượng bit thiết lập mà nó chứa. Nó kiểm tra từng giá trị trong mảng để xem liệu số lượng bit đặt của nó có cao hơn bất kỳ giá trị nào mà nó đã thấy trước đó hay không. Nếu vậy, nó cập nhật các giá trị theo dõi; nếu không, nó sẽ bỏ qua bước này.

Lệnh popcntnày là một lệnh lớn (4 byte), nhưng không thể làm gì để tránh điều đó. Tuy nhiên, lệnh rất ngắn (1 byte) lodsđã được sử dụng để tải các giá trị từ mảng đồng thời tăng con trỏ, lệnh ngắn (2 byte) loopđã được sử dụng để điều khiển vòng lặp (tự động giảm bộ đếm phần tử và lặp lại càng lâu vì có nhiều phần tử còn lại để thực hiện) và lệnh rất ngắn (1 byte) xchgđã được sử dụng xuyên suốt.

Một phần bổ sung xchgđã phải được sử dụng ở cuối để cho phép sử dụng lodslệnh, lệnh này luôn tải vào thanh eaxghi, nhưng sự đánh đổi đó là nhiều hơn giá trị.

Hãy thử nó trực tuyến!

Lần thử đầu tiên của tôi là một hàm 20 byte. Cho đến nay, 18 byte là tốt nhất mà tôi có thể nghĩ ra. Tôi tò mò muốn xem liệu có ai khác có thể đánh bại số điểm này không!

Lộ trình cải tiến duy nhất mà tôi thấy là nếu có một LOOPAchỉ dẫn. Thật không may, nó không — mã điều kiện duy nhất được hỗ trợ LOOPlà E/ Zvà NE/ NZ. Nhưng có lẽ ai đó có thể mở rộng tâm trí của họ xa hơn tôi!

Answer 3

JavaScript (ES6),  49 48 47  45 byte

Đã lưu 2 byte nhờ @ user81655

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

Hãy thử nó trực tuyến!

Làm sao?

Chúng tôi .sort()liệt kê danh sách đầu vào với một hàm đệ quy, cho trước pvà q, xóa tập bit quan trọng nhất trong mỗi biến cho đến khi một trong số chúng bằng 0 (hoặc đồng thời cả hai). Điều này cho phép sắp xếp thứ tự danh sách từ bộ bit nhiều nhất đến ít nhất. Sau đó, chúng tôi trả về mục nhập đầu tiên, tức là mục nhập "bittiest".

Đã nhận xét

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

Answer 4

APL (Dyalog Unicode) , 15 byte

Đã tiết kiệm nhiều byte nhờ Adam và ngn.

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

Hãy thử nó trực tuyến!

Answer 5

C (gcc) , ⁸⁰ 77 byte

Đã lưu 3 byte nhờ vào att !!!

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

Hãy thử nó trực tuyến!

Answer 6

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

145-> 141 nhờ người dùng
128-> 116 nhờ vào trầncat

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

Hãy thử nó trực tuyến!

Answer 7

Kotlin , 41 38 29 byte

Mã đúng với ít byte hơn nhiều :) {Cảm ơn @vrintle}

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

Sân chơi Kotlin

---

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

Sân chơi Kotlin

---

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

Hãy thử nó trực tuyến!

Answer 8

05AB1E , 9 byte

ΣžJ%b1¢}θ

Hãy thử nó trực tuyến!

Σž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

Answer 9

R , 58 55 54 byte

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

Hãy thử nó trực tuyến!

-2 cảm ơn Robin Ryder

-1 cảm ơn Dominic van Essen.

Answer 10

Stax , 18 byte

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

Chạy và gỡ lỗi nó

Đánh dấu thủ công với 1s / 0s để có được biểu diễn chính xác.

Hiển thị một số duy nhất cho mỗi testcase.

Answer 11

K (ngn / k) , 11 byte

{*x@>+/2\x}

Hãy thử nó trực tuyến!

Answer 12

Python 3 , 52 byte

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

Hãy thử nó trực tuyến!

n%2**31- vì trong python số nguyên là vô hạn, phải thay đổi số âm. ví dụ -4trở thành2147483644

bin(...) - dịch sang định dạng nhị phân

count("1") - đếm số lượng đơn vị

---

Python 3 , 50 byte

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

Hãy thử nó trực tuyến!

ngắn hơn hai byte, nhưng không hoạt động với số âm

Answer 13

Scala , 54 42 40 36 byte

Đã lưu một số byte nhờ tính năng chia sẻ tiền ảo kỳ lạ, didymus, người dùng và một số mẹo

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

Hãy thử nó trực tuyến!

Answer 14

Husk , 17 16 13 byte

Chỉnh sửa: -1 byte nhờ Razetime, và sau đó là -3 byte nhờ Leo

►(ΣḋΩ≥0+^32 2

Hãy thử nó trực tuyến!

Husk nguyên bản sử dụng các số nguyên có độ chính xác tùy ý và do đó không có khái niệm về phần bù của 32-bit 2 để biểu diễn các số nguyên có dấu 4 byte âm: do đó, hàm 'lấy các chữ số nhị phân' - ḋ- đáng buồn là ở đây vô dụng đối với các đầu vào âm.
Vì vậy, chúng ta cần tính toán 'bittiness bổ sung của 2' bằng tay.

Cảm ơn sự giúp đỡ của Husk từ Leo để sử dụng Ωở đây.

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

Answer 15

Java 10, 73 byte

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

Hãy thử nó trực tuyến.

Giải trình:

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

Answer 16

Thạch , 9 8 byte

%Ø%BSƲÞṪ

Hãy thử nó trực tuyến!

-1 byte bằng cách sử dụng Þ(sắp xếp) thay vì ÐṀ(tối đa). Điều này được lấy cảm hứng từ câu trả lời của Gio D và sau khi chỉnh sửa của họ và của tôi, cả hai giải pháp đều khá giống nhau.

Giải trình

%Ø%BSƲÞṪ   Main monadic link
      Þ    Sort by
     Ʋ     (
%            Modulo
 Ø%            2^32
   B         Binary
    S        Sum
     Ʋ     )
       Ṫ   Last item

Answer 17

Japt -h , 10 byte

ñÈu2pH)¤¬x

Thử nó

ñÈ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

Answer 18

Perl 5 , 54 byte

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

Hãy thử nó trực tuyến!

Answer 19

Ruby 2.7 , 36 33 34 byte

Cảm ơn Dingus đã sửa mã của tôi cho một trường hợp đặc biệt! :)

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

Hãy thử nó trực tuyến!

Sử dụng args dòng lệnh cho đầu vào, đầu ra số bittiest dưới dạng một chuỗi. TIO sử dụng phiên bản Ruby cũ hơn, trong khi trong Ruby 2.7, chúng tôi đã đánh số các tham số, giúp tiết kiệm hai byte.

Answer 20

Java (JDK) , 44 byte

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

Hãy thử nó trực tuyến!

Đây là một kiểu gian lận, vì nó chấp nhận một Stream<Integer>đầu vào là đầu vào và trả về một Optional<Int>.

Answer 21

Scala , 24 byte

_ maxBy Integer.bitCount

Hãy thử nó trực tuyến!

Tách khỏi câu trả lời đầu tiên tuyệt vời của Gabber .

Answer 22

C # (Visual C # Interactive Compiler) , 71 58 byte

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

Hãy thử nó trực tuyến!

• Đã cấu trúc lại để sử dụng lambda theo đề xuất của @user trong nhận xét

Answer 23

Than củi , 22 byte

≔ＥθΣ⍘﹪ιＸ²¦³²¦²ηＩ§θ⌕η⌈η

Hãy thử nó trực tuyến! Liên kết là phiên bản dài của mã. Giải trình:

≔ＥθΣ⍘﹪ιＸ²¦³²¦²η

Đối với mỗi số trong danh sách, hãy chuyển nó thành một số không dấu 32 bit, chuyển nó thành nhị phân và tính tổng các bit.

Ｉ§θ⌕η⌈η

Xuất ra số ở vị trí đếm bit cao nhất.

Answer 24

SystemVerilog, 66 byte

Đây sẽ là một câu trả lời không hoàn hảo cho bây giờ vì tôi đang đăng bài từ điện thoại của mình, nhưng $countones()chức năng của SV là hoàn hảo ở đây.

function m(int q[$]);
m=q.max with ($countones(item));
endfunction

Answer 25

Ngôn ngữ Wolfram (Mathematica) , 39 byte

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

Hãy thử nó trực tuyến!

Answer 26

PowerShell, 53 56 byte

+5 byte vì nó không xử lý các phủ định đúng cách
-2 byte nhờ mazzy

$args|sort{$v=$_;0..31|%{$o+=!!(1-shl$_-band$v)};$o}-b 1

Answer 27

Nim , 75 byte

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

Hãy thử nó trực tuyến!

Answer 28

Zsh, 85 byte

thử nó trực tuyến!

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

Thử thách lớn, yêu cầu một số Zshcâu thần chú kỳ lạ nhất ! Giải thích:
_{for i;{... lặp lại ngầm định trên tất cả các đối số
$((i<0?[##2]2**32+i:[##2]i))... chuyển đổi isang định dạng 32 bit, sử dụng mẹo bổ sung của hai nếu i<0
${#${(M)${(s::) //expression// }#1}}... mở rộng chuỗi thành mảng, đếm các phần tử mà (M) atch 1
((c>d))&&j=$i&&d=$c... theo dõi đầu vào nào ilà "bittiest" theo số lượng c
<<<$j... xuất ra người chiến thắng}

Answer 29

J , 20 byte

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

Như đã viết, khi cho nhiều số bằng nhau, tối đa là bitty, trả về giá trị đầu tiên trong mảng. Nếu {.\:được thay đổi thành {:/:, nó cho kết quả cuối cùng. Hãy thử nó trực tuyến!

Answer 30

AArch64, 48 44 byte

Hướng dẫn thô (32-bit endian hex):

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

Lắp ráp không chú thích:

        .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

Giải trình

Chữ ký hàm C:

int32_t bittiest(int32_t *words, size_t len);

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

Lệnh đếm dân số của AArch64 ở dạng NEON (bộ lệnh SIMD / dấu phẩy động), và nó đếm từng byte riêng lẻ. Do đó, sẽ hơi khó xử khi làm việc với các ứng dụng vô hướng ở đây vì vậy chúng tôi thực hiện mọi thứ trong NEON.

v4 là số lượng dân số tối đa (v4, s4, h4 và d4 đều tham chiếu đến cùng một thanh ghi). Đặt nó thành 0.

        fmov    s4, #0

Tải từ int32 tiếp theo vào v0 và tăng các từ (x0) lên 4.

        ldr     s0, [x0], #4

Lưu trữ số lượng dân số của mỗi byte trong v0 vào byte tương ứng trong v1.

        cnt     v1.8b, v0.8b

Thêm tất cả các làn 8 bit trong v1 lại với nhau để có tổng số dân đầy đủ và lưu trữ lại vào v1.

        uaddlv  h1, v1.8b

So sánh số lượng dân số của từ này là tối đa. Nếu nó lớn hơn hoặc bằng, v3 sẽ là tất cả các bit 1 (đúng), ngược lại sẽ là tất cả các bit 0 (sai).

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

Nếu v3 là true, hãy đặt từ max (v2) thành từ hiện tại. max không được khởi tạo trong lần lặp đầu tiên, nhưng nó sẽ luôn được đặt vì số lượng dân số sẽ luôn> = 0.

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

Tương tự, nhưng đối với số lượng dân số tối đa mới.

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

Giảm dần len (x1), và lặp lại nếu nó không phải là 0

        subs    x1, x1, #1
        bne     .Lloop

Kết thúc vòng lặp: Di chuyển giá trị lớn nhất từ ​​thanh ghi NEON sang thanh ghi trả về (w0) và quay trở lại.

        fmov    w0, s2
        ret

11 hướng dẫn = 44 byte