37
\$\begingroup\$

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.

Write a function (or a program) that takes as input a list 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

Input: 1, 2, 3, 4

Output: 3

Input: 123, 64, 0, -4

Output: -4

Input: 7, 11

Output: Either 7 or 11 (but not both)

Input: 1073741824, 1073741823

Output: 1073741823

Good Luck

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

Clarification

If your language doesn't support 32-bit signed integers, you may use any other numeric (read: not textual) representation as long as it can represent all integers from -2^31 to 2^31 - 1 inclusive, using two's complement for negatives.

\$\endgroup\$
23
  • 3
    \$\begingroup\$ If our language has no 32-bit signed integers should we accept integers (and perform manipulations) or may we accept a list of ones and zeros (what a 32-bit signed integer actually is under the hood)? \$\endgroup\$ Dec 19, 2020 at 20:42
  • 3
    \$\begingroup\$ I'd suggest adding larger test cases where it matters that we're using 32-bit signed integers for two's complement, and not say 16 or 64. \$\endgroup\$
    – xnor
    Dec 19, 2020 at 22:38
  • 11
    \$\begingroup\$ @Bip, one of the standard rules around here is not to assume anything about the functionality of a language. There are languages where integers are unsigned, other sizes, or don't exist at all. It's not necessarily a primitive data type. \$\endgroup\$
    – Xcali
    Dec 19, 2020 at 23:49
  • 13
    \$\begingroup\$ I think a clearer way to specify the challenge without making language assumptions is to say the input is a list of integers between -2^31 and 2^31-1, and we output one whose 32-bit signed representation has the most 1's. \$\endgroup\$
    – xnor
    Dec 20, 2020 at 0:04
  • 4
    \$\begingroup\$ @qwr But then its inverse would not be the "itty-bittiest number". \$\endgroup\$
    – beaker
    Dec 21, 2020 at 16:51

31 Answers 31

26
\$\begingroup\$

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!

\$\endgroup\$
10
  • \$\begingroup\$ xchg edx, edi could be a more efficient mov edx, edi for no change in code size, but that's not worth editing for. This same machine code also works in 64-bit mode, with 64-bit pointers / count, and still an array of uint32_t. I don't see any further savings, but maybe we're both missing something. \$\endgroup\$ Dec 21, 2020 at 0:27
  • \$\begingroup\$ In 64-bit mode, this code can be called from C as int bittiest(int dummy_edi, const int32_t *arr /*RSI*/, int dummy_edx, size_t size /*RCX*/); following the x86-64 System V calling convention except for clobbering EBX. (Avoiding that would cost extra bytes for r8d, or push/pop). You could save a byte by returning in EBX instead of EAX: Tips for golfing in x86/x64 machine code \$\endgroup\$ Dec 21, 2020 at 18:18
  • \$\begingroup\$ @Peter I assume you mean that mov edx, edi would be more efficient than the equivalent xchg, without requiring any more bytes to encode? Yeah, that's a good point. I didn't even think of that. I would never use xchg for anything but code golf, and since I was already planning to use it for the 1-byte encoding using the accumulator, I just over-eagerly used it everywhere. Indeed, the code works well with 64-bit; I had originally written it that way, then decided that there was no good reason to pay the instruction size penalty. In 64-bit mode, though, you get more caller-save registers. \$\endgroup\$
    – Cody Gray
    Dec 22, 2020 at 6:01
  • 1
    \$\begingroup\$ Regarding returning in EBX, I felt like that was pushing things a bit too far, since literally every x86 calling convention that exists returns results in EAX. I don't mind defining my own calling conventions for passing parameters, but I like to stick as close as possible to something that is reasonable, even when golfing. Maybe that's just my own idiosyncrasies. It really bothers me when people submit golfing entries that rely on compiler-specific behavior, like omitting a "return". \$\endgroup\$
    – Cody Gray
    Dec 22, 2020 at 6:03
  • 2
    \$\begingroup\$ Return in EBX might hurt most hand-written golfed asm programs overall, but I see it as perfectly valid to leave the return value anywhere the caller can use it conveniently. (e.g. a boolean in FLAGS like *BSD and MacOS syscalls). And to clobber as many regs as I want. But I don't have any problem with you choosing different standards for what you think is sane or the kind of problem-space you want to golf in; that's just how I think about it, in a way that makes sense to me while still agreeing with you about that lame trend to golf in "unoptimized-gcc" instead of standard GNU C. \$\endgroup\$ Dec 22, 2020 at 6:11
18
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Would !p|-!q||g(p&p-1,q&q-1) work? \$\endgroup\$
    – user81655
    Dec 22, 2020 at 8:03
  • \$\begingroup\$ @user81655 Nice! The main difference is that q is considered to have less bits set than p when they actually have as many bits set. But this is compatible with the challenge rules. Thank you! \$\endgroup\$
    – Arnauld
    Dec 22, 2020 at 11:29
10
\$\begingroup\$

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Ṁị
\$\endgroup\$
4
  • 4
    \$\begingroup\$ Welcome to Code Golf, nice first answer! Don't usually see first posts in Jelly :p \$\endgroup\$ Dec 21, 2020 at 7:12
  • \$\begingroup\$ I think the should be before the B. And you can use § instead of S€. \$\endgroup\$
    – xigoi
    Dec 21, 2020 at 14:29
  • \$\begingroup\$ The reason why this doesn't work is that iṀ will search for the maximum of the original list. \$\endgroup\$
    – xigoi
    Dec 21, 2020 at 14:32
  • \$\begingroup\$ While you edited the answer, the "Try it online" link still uses the previous, incorrect code. Consider updating it. \$\endgroup\$
    – Bip
    Dec 22, 2020 at 13:27
9
\$\begingroup\$

APL (Dyalog Unicode), 15 bytes

Saved many bytes thanks to Adam and ngn.

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

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Is the byte count correct? The code line above has 15 characters and TIO shows 17 characters \$\endgroup\$
    – Graham
    Dec 20, 2020 at 18:30
  • \$\begingroup\$ @Graham I accidentally subtracted 2 twice, now it should be okay. \$\endgroup\$ Dec 20, 2020 at 18:47
8
\$\begingroup\$

C (gcc), 80 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!

\$\endgroup\$
9
  • \$\begingroup\$ 77 bytes, returning the first rather than last occurence. \$\endgroup\$
    – att
    Dec 20, 2020 at 3:36
  • 3
    \$\begingroup\$ nice use of __builtin_popcount, I bet this one is the fastest and can be used to compile to the smallest machine code. \$\endgroup\$
    – Anunay
    Dec 20, 2020 at 8:26
  • \$\begingroup\$ @att Nice recursive one - thanks! :-) \$\endgroup\$
    – Noodle9
    Dec 20, 2020 at 10:41
  • 2
    \$\begingroup\$ I was working on this, but your's is much golfier. +1 \$\endgroup\$ Dec 20, 2020 at 16:46
  • 2
    \$\begingroup\$ Ah that makes more sense, I forgot to look at edit history and timestamps for major changes to this answer. Makes sense it was from before there was a machine-code answer. \$\endgroup\$ Dec 21, 2020 at 6:11
7
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 141 bytes by removing spaces after #include and by declaring c with i,b,v. Also, you can use a method instead of accepting input from STDIN and printing it. \$\endgroup\$
    – user
    Dec 21, 2020 at 16:02
  • \$\begingroup\$ Thanks @user was able to strip another byte after adding your suggestion. \$\endgroup\$
    – Zaiborg
    Dec 21, 2020 at 16:43
  • 3
    \$\begingroup\$ Welcome to the site, nice first answer! :-) \$\endgroup\$
    – vrintle
    Dec 21, 2020 at 17:44
  • \$\begingroup\$ Thanks @vrintle \$\endgroup\$
    – Zaiborg
    Dec 21, 2020 at 17:49
6
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to the site, nice first answer! However, it fails on the second test case. Here is a 50 byter alternative to it ;-) \$\endgroup\$
    – vrintle
    Dec 21, 2020 at 16:35
6
\$\begingroup\$

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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Shouldn't it be modulo 2^32 instead of 2^31? \$\endgroup\$
    – xigoi
    Dec 21, 2020 at 14:00
  • 2
    \$\begingroup\$ @KevinCruijssen If I'm not mistaken, the two's complement representation of a signed integer n is an unsigned integer that equals n for positive n and 2^32 + n for negative n. \$\endgroup\$
    – xigoi
    Dec 21, 2020 at 15:41
  • 1
    \$\begingroup\$ Here's a simple C program to test it out: Try it online! \$\endgroup\$
    – xigoi
    Dec 21, 2020 at 15:47
  • 1
    \$\begingroup\$ @xigoi Ahh. I was thinking in the wrong direction when I made my comment earlier. Thanks for the added C program as example, now it's clearer what you meant and where my error lies. In that case the 05AB1E program above is indeed slightly incorrect, but can be fixed without changing the byte-count by changing the žI to žJ. \$\endgroup\$ Dec 21, 2020 at 16:23
  • 2
    \$\begingroup\$ You should tank @xigoi, not me. :) And yes, that Python answer is also incorrect in that case. The 2**31 should be 2**32. \$\endgroup\$ Dec 21, 2020 at 20:34
4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ 55 bytes, unless I'm missing something. \$\endgroup\$ Dec 19, 2020 at 22:41
  • \$\begingroup\$ @RobinRyder i assumed sapply wouldn't return a matrix for length one input! \$\endgroup\$
    – Giuseppe
    Dec 19, 2020 at 23:34
  • 1
    \$\begingroup\$ 54 bytes...? \$\endgroup\$ Dec 19, 2020 at 23:45
  • \$\begingroup\$ @DominicvanEssen very nice, thanks. \$\endgroup\$
    – Giuseppe
    Dec 20, 2020 at 1:17
  • \$\begingroup\$ @DominicvanEssen You should add that as a tip! \$\endgroup\$ Dec 20, 2020 at 7:26
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ winner for most interesting to look at :) \$\endgroup\$
    – alec
    Dec 21, 2020 at 15:23
  • \$\begingroup\$ there are a variety of answers provided here that use characters I've never seen in used in code before.... I wonder what they're all about. Are they unique to "golfing" languages? \$\endgroup\$
    – alec
    Dec 21, 2020 at 15:28
  • 2
    \$\begingroup\$ @alec in order to make commands as short as possible, each language developer make a codepage so they can fit a lot of commands within a single byte. Stax uses CP437, which has a lot of weird unrelated characters, including box drawing characters, which makes it look rather distinctive. \$\endgroup\$
    – Razetime
    Dec 21, 2020 at 16:20
4
\$\begingroup\$

K (ngn/k), 11 bytes

{*x@>+/2\x}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
11
  • 2
    \$\begingroup\$ Welcome to the site, and nice first answer! Be sure to check out our Tips for golfing in Scala page! \$\endgroup\$ Dec 21, 2020 at 20:00
  • 1
    \$\begingroup\$ You can reduce the size by one, if you replace '1' with 49. \$\endgroup\$
    – didymus
    Dec 21, 2020 at 20:31
  • 1
    \$\begingroup\$ Replacing _=='1' with _>48, reduces size by 2 bytes \$\endgroup\$
    – didymus
    Dec 21, 2020 at 20:33
  • 1
    \$\begingroup\$ Nice answer! You can get 36 bytes with underscores and postfix syntax. \$\endgroup\$
    – user
    Dec 21, 2020 at 20:57
  • 1
    \$\begingroup\$ Actually, make that 24 bytes using Integer.bitCount. \$\endgroup\$
    – user
    Dec 21, 2020 at 20:59
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ -1 (why do you need to increment the negative integers?) \$\endgroup\$
    – Razetime
    Dec 20, 2020 at 9:34
  • \$\begingroup\$ @Razetime Thanks! Minus 3 is '1011111...' in 2's-complement, so it's the NOT of the bits of plus 2, and so on, hence the need to increment before the bit-count. I think... \$\endgroup\$ Dec 20, 2020 at 10:53
  • 1
    \$\begingroup\$ @Razetime (but maybe you'll be able to make the 'add 2^32' approach... (see Husk chatroom...) \$\endgroup\$ Dec 20, 2020 at 10:55
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Me either, @AZTECCO, first read through. I immediately typed up the exact same solution. \$\endgroup\$
    – Shaggy
    Dec 21, 2020 at 23:00
2
\$\begingroup\$

Perl 5, 54 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ sort{$f{$b}-$f{$a}} saves 2 \$\endgroup\$
    – mob
    Dec 21, 2020 at 14:59
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Unfortunately this approach doesn't work in general because you're counting 1s beyond the 32-bit representation of the number. An extreme example is inputs of 2147483647 and -1073741824, for which the correct output is 2147483647. \$\endgroup\$
    – Dingus
    Dec 20, 2020 at 22:38
  • 1
    \$\begingroup\$ Something like this should work I think. \$\endgroup\$
    – Dingus
    Dec 20, 2020 at 22:40
  • \$\begingroup\$ @Dingus - Hm, it's a little longer, but I would like to know how it works. Also, then 032b will work? \$\endgroup\$
    – vrintle
    Dec 21, 2020 at 2:31
  • 2
    \$\begingroup\$ It's taking the sum of the codepoints of the last 32 characters. Surprisingly enough, 032b doesn't work: ("%032b"%(2147483647)).bytes.size returns 32 but ("%032b"%(-1073741824)).bytes.size returns 33, apparently because of the leading ... However, you can use 034b and then this is 2 bytes shorter than my earlier attempt. \$\endgroup\$
    – Dingus
    Dec 21, 2020 at 2:49
  • 1
    \$\begingroup\$ @Dingus - I will ask the OP for this, and also suggest this testcase. \$\endgroup\$
    – vrintle
    Dec 21, 2020 at 4:20
2
\$\begingroup\$

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>.

\$\endgroup\$
2
\$\begingroup\$

Scala, 24 bytes

_ maxBy Integer.bitCount

Try it online!

Split off from Gabber's great first answer.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ A lambda would make this 58 bytes \$\endgroup\$
    – user
    Dec 21, 2020 at 21:04
  • \$\begingroup\$ Is that allowed by the rules? \$\endgroup\$
    – didymus
    Dec 21, 2020 at 23:54
  • \$\begingroup\$ Why wouldn't it be? \$\endgroup\$
    – user
    Dec 22, 2020 at 0:05
  • \$\begingroup\$ I thought it shouldn’t because it isn’t a function nor a program. \$\endgroup\$
    – didymus
    Dec 22, 2020 at 0:12
  • 1
    \$\begingroup\$ No, lambdas are fine - they're basically functions. There should be a meta question somewhere, but I can't find it right now. \$\endgroup\$
    – user
    Dec 22, 2020 at 0:25
1
\$\begingroup\$

Charcoal, 22 bytes

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

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

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

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

I§θ⌕η⌈η

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 39 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ It does not work with negative integers. Because -1 -shr 1 never be the 0. See test case 123, 64, 0, -4 \$\endgroup\$
    – mazzy
    Dec 21, 2020 at 0:44
  • 1
    \$\begingroup\$ I think we can to use features ot the latest Powershell version by default. For example ...|sort -top 1 instead (...|sort)[-1]. Try it online! \$\endgroup\$
    – mazzy
    Dec 21, 2020 at 0:53
  • \$\begingroup\$ you can use %2 instead operator -band. see Try it online! again. \$\endgroup\$
    – mazzy
    Dec 22, 2020 at 15:08
  • \$\begingroup\$ Unless I'm missing something, that method doesn't work. It works for the case provided because sort sorts ascending by default, and top 1 takes the first element of -30 for -4; you'd need the absolute value of $c to return to sort, and you'd need to still select the bottom 1. Try it online! \$\endgroup\$ Dec 22, 2020 at 15:54
  • 1
    \$\begingroup\$ @mazzy sorry, that last tio for my example was all janked up because I tried to adapt from a different one I was working on. This one should demonstrate more clearly: Try it online! \$\endgroup\$ Dec 22, 2020 at 16:06
1
\$\begingroup\$

Nim, 75 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Zsh, 85 bytes

try it online!

for i;{c=${#${(M)${(s::)$((i<0?[##2]2**32+i:[##2]i))}#1}}
((c>d))&&j=$i&&d=$c;}
<<<$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
${#${(M)${(s::) //expression// }#1}} ... expand string to array, count elements that (M)atch 1
((c>d))&&j=$i&&d=$c ... keep track of which input i is the "bittiest" according to the count c
<<<$j ... output the winner

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
1
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to the site! Could you separate the code from the other stuff to make things a little easier to read? One big code block is a little hard to understand at least for me. \$\endgroup\$
    – Wheat Wizard
    Dec 23, 2020 at 8:56
  • \$\begingroup\$ Is that what you meant? I also added the compiled version. \$\endgroup\$
    – EasyasPi
    Dec 23, 2020 at 15:43
  • 1
    \$\begingroup\$ Yeah that and the explanation are really helpful. Nice answer! \$\endgroup\$
    – Wheat Wizard
    Dec 23, 2020 at 16:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.