找出“最坏”的数字

Question

挑战

给定一个整数列表，其中的“最比特”数是位数最多的一个，也就是设置为1的最大位数。

编写一个函数(或程序)，该函数以32位有符号整数的列表作为输入，并将其中“最”的数字作为输出返回。

您可以假设列表至少有一项。

测试用例

输入：1, 2, 3, 4

输出：3

输入：123, 64, 0, -4

输出：-4

输入：7, 11

输出：7或11 (但不是两者兼备)

输入：1073741824, 1073741823

输出：1073741823

好运

这是代码高尔夫，所以最短的程序以字节为单位获胜。

Clarification

如果您的语言不支持32位有符号整数，您可以使用任何其他数字(读:而不是文本)表示，只要它可以表示从-2^31到2^31 - 1包含的所有整数，对负数使用二补。

Answer 1

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寄存器中的参数，但在其他情况下，它很像一个C函数，它将数组的长度和指向数组的指针作为其两个参数。此自定义调用约定将所有寄存器视为调用方保存，包括ebx。

该函数的实现使用了一些肮脏的技巧，这些技巧假设数组至少有一个元素，这是在挑战中提供的。它还假定方向标志(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

当然，这段代码的关键特性是x86 popcnt指令，它计算整数中的集合位数。它遍历输入数组，跟踪最大元素的值和包含的集合位数。它检查数组中的每个值，以查看其设置位数是否高于它以前看到的任何值。如果是，则更新跟踪值；如果不更新，则跳过此步骤。

popcnt指令是一个大的(4字节)指令，但是没有什么可以避免的。但是，非常短的(1字节) lods指令已用于从数组加载值，同时递增指针，短(2字节) loop指令用于循环控制(只要有更多的元素需要通过，则自动递减元素计数器和循环)，并且非常短的(1字节) xchg指令一直被使用。

最后必须使用一个额外的xchg，以便能够使用lods指令，该指令总是加载到eax寄存器中，但这种权衡是非常值得的。

在网上试试！

我的第一次尝试是一个20字节的函数。到目前为止，18个字节是我所能想到的最好的。我很想看看是否还有其他人能战胜这个分数！

我看到的唯一改进的途径是如果存在LOOPA指令。不幸的是，它没有-- LOOP支持的唯一条件代码是E/Z和NE/NZ。但也许其他人会比我更能扩展他们的思想！

Answer 2

Dyalog Unicode，15字节

多亏了Adam和ngn，节省了很多字节。

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

在网上试试！

Answer 3

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