x86-64 Machine Code, 22 bytes
48 B8 41 92 34 6D DB F7 FF FF 83 F9 40 7D 03 48 D3 E8 83 E0 01 C3
The above bytes define a function in 64-bit x86 machine code that determines whether the input value is a Chicken McNugget number. The single positive integer parameter is passed in the ECX
register, following the Microsoft 64-bit calling convention used on Windows. The result is a Boolean value returned in the EAX
register.
Ungolfed assembly mnemonics:
; bool IsMcNuggetNumber(int n)
; n is passed in ECX
movabs rax, 0xFFFFF7DB6D349241 ; load a 64-bit constant (the bit field)
cmp ecx, 64
jge TheEnd ; if input value >= 64, branch to end
shr rax, cl
TheEnd:
and eax, 1 ; mask off all but LSB
ret
Obviously, this plays heavily off of Anders Kaseorg's solution in Python, in that it is based around a bit-field representing the values that are Chicken McNugget numbers. Specifically, each bit in this field that corresponds to a valid Chicken McNugget number is set to 1; all other bits are set to 0. (This considers 0 to be a valid Chicken McNugget number, but if you don't like that, your preference is a single-bit modification away.)
We start off by simply loading this value into a register. It is a 64-bit value, which already takes 8 bytes to encode, plus we need a one-byte REX.W prefix, so we are really being quite spendthrift in terms of bytes, but this is the heart of the solution, so I guess it's worth it.
We then shift the field right by the input value.* Finally, we mask off all but the lowest-order bit, and that becomes our Boolean result.
However, since you cannot shift by more than the number of bits actually in the value, this works only for inputs from 0–63. To support higher input values, we insert a test at the top of the function that branches to the bottom of the input value is >= 64. The only thing interesting about this is the we preload the bit-field constant in RAX
, and then branch down to the instruction that masks off the lowest-order bit, thus ensuring that we always return 1.
Try it online!
(The C function call there is annotated with an attribute that causes GCC to call it using the Microsoft calling convention that my assembly code uses. If TIO had provided MSVC, this wouldn't be necessary.)
__
* As an alternative to a shift, we could have used the x86 BT
instruction, but that's 1 byte longer to encode, so no advantage. Unless we were forced to use a different calling convention that didn't conveniently pass the input value in the ECX
register. This would be a problem because SHR
requires that its source operand be CL
for a dynamic shift count. Therefore, a different calling convention would require that we MOV
ed the input value from whatever register it was passed in to ECX
, which would cost us 2 bytes. The BT
instruction can use any register as a source operand, at a cost of only 1 byte. So, in that situation, it would be preferable. BT
puts the value of the corresponding bit into the carry flag (CF), so you would use a SETC
instruction to get that value in an integer register like AL
so it could be returned to the caller.
Alternative implementation, 23 bytes
Here is an alternative implementation that uses modulo and multiplication operations to determine whether the input value is a Chicken McNugget number.
It uses the System V AMD64 calling convention, which passes the input value in the EDI
register. The result is still a Boolean, returned in EAX
.
Note, though, that unlike the above code, this is an inverse Boolean (for implementation convenience). It returns false
if the input value is a Chicken McNugget number, or true
if the input value is not a Chicken McNugget number.
; bool IsNotMcNuggetNumber(int n)
; n is passed in EDI
8D 04 3F lea eax, [rdi+rdi*1] ; multiply input by 2, and put result in EAX
83 FF 2B cmp edi, 43
7D 0E jge TheEnd ; everything >= 43 is a McNugget number
99 cdq ; zero EDX in only 1 byte
6A 03 push 3
59 pop rcx ; short way to put 3 in ECX for DIV
F7 F1 div ecx ; divide input value by 3
6B D2 14 imul edx, edx, 20 ; multiply remainder of division by 20
39 D7 cmp edi, edx
0F 9C C0 setl al ; AL = (original input) < (input % 3 * 20)
TheEnd:
C3 ret
What's ugly about this is the need to explicitly handle input values >= 43 by a compare-and-branch at the top. There are obviously other ways of doing this that don't require branching, like caird coinheringaahing's algorithm, but this would take a lot more bytes to encode, so isn't a reasonable solution. I figure I'm probably missing some bit-twiddling trick that would make this work out more elegantly and be fewer bytes than the bitfield-based solution above (since encoding the bitfield itself takes so many bytes), but I've studied this for a while and still can't see it.
Oh well, try it online anyway!
15
It should be noted that "All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43." (mathworld)
– Leaky Nun – 2017-07-16T18:06:38.3231Well, then let's take it as a compression challenge, but thanks for the note – racer290 – 2017-07-16T18:08:24.187
@Leaky Nun Also, I haven't spotted a proof for that yet.. – racer290 – 2017-07-16T18:14:43.067
1@racer290 With
6
and9
you can get to any multiple of3
which is>3
. By subtracting0
,20
,40
from your number you will get to a multiple of3
and therefore there can't be any McNuggets number>43
. – ovs – 2017-07-16T18:21:26.253Related – HyperNeutrino – 2017-07-16T18:21:44.267
@HyperNeutrino Hell yea when i posted it on meta another one was mentioned but not this one. – racer290 – 2017-07-16T18:27:15.043
3Anybody have an OEIS link for this??? – CraigR8806 – 2017-07-17T11:44:50.883
2
What do you have against the 4 piece nugget pack? https://www.mcdonalds.com/us/en-us/product/chicken-mcnuggets-4-piece.html
– Dan is Fiddling by Firelight – 2017-07-17T19:25:51.003@LeakyNun it's not a competitive approach though heh... https://codegolf.stackexchange.com/a/132856/59376
– Magic Octopus Urn – 2017-07-17T22:16:57.5832numberphile... – Jason C – 2017-07-17T22:20:22.973