Find the "Bittiest" Number

Question

The Challenge

Given a list of integers, the "bittiest" number among them is the one with the most bits on - that is, the largest amount of bits set to 1 in its 32-bit two's complement representation.

Write a function (or a program) that takes as input a list of integers between \$ -2^{31} \$ and \$ 2^{31}-1 \$ (the range of 32-bit signed integers) and returns as output the "bittiest" number among them.

You may assume the list has at least one item.

Test Cases

1, 2, 3, 4 => 3
123, 64, 0, -4 => -4
7, 11 => either 7 or 11
1073741824, 1073741823 => 1073741823

Good Luck!

This is code golf, so the shortest program in bytes wins.

Answer 1

x86 Machine Language, 18 bytes

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

The above bytes define a function that accepts the address of the array in the esi register and the number of elements in the array in the ecx register, and returns the "bittiest" number in the array in the eax register.

Note that this is a custom calling convention that accepts arguments in the ecx and esi registers, but it is otherwise much like a C function that takes the length of the array and a pointer to the array as its two arguments. This custom calling convention treats all registers as caller-save, including ebx.

The implementation of this function pulls some dirty tricks, which assume that the array has at least 1 element, as provided for in the challenge. It also assumes that the direction flag (DF) is clear (0), which is standard in all calling conventions that I'm aware of.

In ungolfed assembly-language mnemonics:

; 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

The key feature of this code is, of course, the x86 popcnt instruction, which counts the number of set bits in an integer. It iterates through the input array, keeping track of both the value of the maximum element and the number of set bits that it contains. It checks each value in the array to see if its number of set bits is higher than any value it has seen before. If so, it updates the tracking values; if not, it skips this step.

The popcnt instruction is a large (4-byte) instruction, but there's nothing that can be done to avoid that. However, the very short (1-byte) lods instruction has been used to load values from the array while simultaneously incrementing the pointer, the short (2-byte) loop instruction has been used for loop control (automatically decrementing the element counter and looping as long as there are more elements remaining to go through), and the very short (1-byte) xchg instruction has been used throughout.

An extra xchg had to be used at the end in order to enable use of the lods instruction, which always loads into the eax register, but that trade-off is more than worth it.

Try it online!

My first attempt was a 20-byte function. So far, 18 bytes is the best I have been able to come up with. I'm curious to see if anyone else can beat this score!

The only route of improvement that I see would be if a LOOPA instruction existed. Unfortunately, it doesn't—the only condition codes supported by LOOP are E/Z and NE/NZ. But maybe someone else can stretch their mind further than me!

Answer 2

JavaScript (ES6),  49 48 47  45 bytes

Saved 2 bytes thanks to @user81655

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

Try it online!

How?

We .sort() the input list with a recursive function that, given p and q, clears the least significant bit set in each variable until one of them is equal to 0 (or both of them simultaneously). This allows to order the list from most to least bits set. We then return the first entry, i.e. the "bittiest" one.

Commented

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 3

Jelly, 13 12 8 bytes

%Ø%B§µÞṪ

Try it online!

Explanation

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

Edit: thank you all for the kind response to my first question! I think I've fixed it now, it seems to work for all test cases.

Original code

2*31
B%¢S€iṀị

Answer 4

APL (Dyalog Unicode), 15 bytes

Saved many bytes thanks to Adam and ngn.

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

Try it online!

Answer 5

C (gcc), ⁸⁰ 77 bytes

Saved 3 bytes thanks to att!!!

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

Try it online!

Answer 6

Kotlin, 41 38 29 bytes

Correct code with much fewer bytes :) { Thanks @vrintle }

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

Kotlin Playground

---

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

Kotlin Playground

---

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

Try it online!

Answer 7

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

145->141 thanks to user
128->116 thanks to 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;}

Try it online!

Answer 8

05AB1E, 9 bytes

ΣžJ%b1¢}θ

Try it online!

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

K (ngn/k), 11 bytes

{*x@>+/2\x}

Try it online!

Answer 10

R, 58 55 54 bytes

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

Try it online!

-2 thanks to Robin Ryder

-1 thanks to Dominic van Essen.

Answer 11

Stax, 18 bytes

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

Run and debug it

Manually pads with 1s/0s to get the correct representation.

Displays a single number for each testcase.

Answer 12

Python 3, 52 bytes

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

Try it online!

n%2**31 - since in python integers are infinite, have to change negative numbers. for example -4 becomes 2147483644

bin(...) - translate to binary format

count("1") - count the number of units

---

Python 3, 50 bytes

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

Try it online!

two bytes shorter, but doesn't work with negative numbers

Answer 13

Scala, 54 42 40 36 bytes

Saved some bytes thanks to caird coinheringaahing, didymus, user, and some tips

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

Try it online!

Answer 14

Husk, 17 16 13 bytes

Edit: -1 byte thanks to Razetime, and then -3 bytes thanks to Leo

►(ΣḋΩ≥0+^32 2

Try it online!

Husk natively uses arbitrary-precision integers, and so has no notion of 32-bit 2's complement for representing negative 4-byte signed integers: as a result, the 'get binary digits' function - ḋ - is sadly useless here for negative inputs.
So we need to calculate the '2's complement bittiness' by hand.

Thanks to Husk help from Leo for the use of Ω here.

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

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

Try it online.

Explanation:

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

Jelly, 9 8 bytes

%Ø%BSƲÞṪ

Try it online!

-1 byte by using Þ (sort) instead of ÐṀ (maximum). This was inspired by Gio D's answer and after their and my edit, both solutions are pretty much the same.

Explanation

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

Answer 17

Japt -h, 10 bytes

ñÈu2pH)¤¬x

Try it

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

Ruby 2.7, 36 33 34 bytes

Thanks to Dingus for correcting my code for a special case! :)

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

Try it online!

Uses command-line args for input, outputs the bittiest number as a string. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

Answer 19

Java (JDK), 44 bytes

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

Try it online!

This is kind of cheating, as it accepts a Stream<Integer> as input and returns an Optional<Int>.

Answer 20

Scala, 24 bytes

_ maxBy Integer.bitCount

Try it online!

Split off from Gabber's great first answer.

Answer 21

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

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

Try it online!

• Refactored to use a lambda as suggested by @user in comments

Answer 22

Perl 5 -pa, 54 45 bytes

map$a[(sprintf"%b",$_)=~y/1//]=$_,@F;$_=pop@a

Try it online!

Answer 23

Zsh, 71 bytes

Try it Online!  _{81bytes  85bytes}

for i;a=${$((i<0?[##2]2**32+i:[##2]i))//0}&&(($#a>b?(j=i,b=$#a)))
<<<$j

Great challenge, required some of the weirdest Zsh incantations! Explanation:
_{for i; ... implicit iteration over all arguments
$((i<0?[##2]2**32+i:[##2]i)) ... convert i to 32-bit format, using two's complement trick if i<0
a=${ ~string~ //0} ... remove all 0s from string
(($#a>b?(j=i,b=$#a))) ... keep track of which input i is the "bittiest" according to the length of string a
<<<$j ... output the winner}

Answer 24

Charcoal, 22 bytes

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

Try it online! Link is to verbose version of code. Explanation:

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

For each number in the list, cast it to a 32-bit unsigned number, convert it to binary, and sum the bits.

Ｉ§θ⌕η⌈η

Output the number at the position of the highest bit count.

Answer 25

SystemVerilog, 66 bytes

This will be an imperfect answer for now as I’m posting from my phone, but SV’s$countones() function is perfect here.

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

Answer 26

Wolfram Language (Mathematica), 39 bytes

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

Try it online!

Answer 27

PowerShell, 53 56 bytes

+5 bytes because it did not handle negatives properly
-2 bytes thanks to mazzy

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

Answer 28

Nim, 75 bytes

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

Try it online!

Answer 29

J, 20 bytes

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

As written, when given multiple equally, maximally bitty numbers, returns the first in the array. If {.\: is changed to {:/:, it gives the last. Try it online!

Answer 30

AArch64, 48 44 bytes

Raw instructions (32-bit little endian hex):

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

Uncommented assembly:

        .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

Explanation

C function signature:

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

AArch64's population count instruction is in NEON (the SIMD/floating point instruction set), and it counts each byte individually. Therefore, it is a little awkward to work with scalars here so we do everything in NEON.

v4 is the max population count (v4, s4, h4, and d4 all refer to the same register). Set it to 0.

        fmov    s4, #0

Load the next int32 word into v0, and increment words (x0) by 4.

        ldr     s0, [x0], #4

Store the population count of each byte in v0 into the corresponding byte in v1.

        cnt     v1.8b, v0.8b

Add all of the 8-bit lanes in v1 together to get the full population count, and store into v1 again.

        uaddlv  h1, v1.8b

Compare the population count of this word to the maximum. If it is larger or equal, v3 will be all 1 bits (true), otherwise it will be all 0 bits (false).

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

If v3 is true, set the max word (v2) to the current word. max is not initialized on the first iteration, but it will always be set because the population count will always be >= 0.

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

Same, but for the new max population count.

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

Decrement len (x1), and loop if it is not zero

        subs    x1, x1, #1
        bne     .Lloop

End of loop: Move the maximum value from a NEON register to the return register (w0), and return.

        fmov    w0, s2
        ret

11 instructions = 44 bytes