Поплавок 754 до Хэмминга

29

В качестве входных данных вы получите целое число kв диапазоне от -4503599627370496(−2 52 ) до 4503599627370496(2 52 ). Как хорошо известно , целые числа в этом диапазоне могут быть представлены в точности как значения с плавающей запятой двойной точности.

Вы должны выход на вес Хемминга (количество единиц) в кодировании kв формате binary64 . При этом используется 1 бит для знака, 11 бит для показателя степени (закодированный со смещением) и 52 для мантиссы; см. ссылку выше для деталей.

В качестве примера , число 22представляется как

0 10000000011 0110000000000000000000000000000000000000000000000000

Так как есть 5, выход 5.

Обратите внимание, что порядковый номер не влияет на результат, поэтому вы можете безопасно использовать фактическое внутреннее представление вашей машины значений двойной точности для вычисления выходных данных.

Дополнительные правила

Контрольные примеры

22                ->   5
714               ->   6
0                 ->   0
1                 ->  10
4503599627370496  ->   5
4503599627370495  ->  55
1024              ->   3
-1024             ->   4
-4096             ->   5
1000000000        ->  16
-12345678         ->  16
Луис Мендо
источник
1
Вы намерены, что функции могут принимать свои входные данные уже в binary64формате с плавающей запятой , если они хотят? Некоторые люди (в том числе и я изначально) интерпретировали этот вопрос как требование, чтобы функции принимали входные данные как целочисленный тип, например Си long. В C вы можете утверждать, что язык будет конвертировать для вас, так же, как когда вы звоните sqrt((int)foo). Но есть некоторые ответы asm для машинного кода x86 (например, codegolf.stackexchange.com/a/136360/30206 и мой), которые оба предполагали, что нам нужно принять 64-битные целочисленные входные данные. Принятие binary64значения сохранит 5 байтов.
Питер Кордес
Если так, то все эти вещи с ограниченным диапазоном - на тот случай, если кто-то хочет взломать преобразование в двоичную 64-битную комбинацию самостоятельно вместо наложения типа? Или для языков без ввода текста? Хм, интересной задачей может быть добавление экспоненты и мантиссы в качестве binary64целых чисел base2. В любом случае, если вам нужно обрабатывать их отдельно, возможно, стоит сделать что-то иное, нежели тип-каламбур и цикл по всем битам.
Питер Кордес
2
@PeterCordes Да, вы можете ввести в виде числа с плавающей точкой. Ограниченный диапазон должен гарантировать, что представление с плавающей точкой является точным
Луис Мендо
Хорошо спасибо. Я думаю, вы хотели оставить возможность написать функцию, которая принимает a long, так что вы не могли бы просто сказать что-нибудь двоичное64 double, потому что не все двойные числа являются целыми числами. Но все целочисленные doubles могут быть преобразованы в longи обратно, вплоть до пределов long. (Как вы указали, обратное неверно. Вы получаете ближайшее представление double, предполагая режим округления по умолчанию). Во всяком случае, это был совершенно правильный способ задать вопрос; Я просто не прочитал это внимательно>. <
Питер Кордес
«Обратите внимание, что порядок байтов не влияет на результат, поэтому вы можете безопасно использовать фактическое внутреннее представление вашей машины значений двойной точности для вычисления результата». если ваша машина не использует формат IEEE с плавающей запятой ...
Джерри Иеремия

Ответы:

8

MATL , 5 байтов

3Z%Bz

Попробуйте онлайн!

Точная транслитерация моего ответа в MATLAB. Обратите внимание, что ввод и вывод неявны. -2 байта благодаря Луису Мендо.

3Z%   % Typecast: changes input (implicitly taken and converted to double) to uint64 without changing underlying bits
B     % Convert integer to array of 1s and 0s
z     % Count nonzero entries
Sanchises
источник
33

машинный язык x86_64 (Linux), 16 байт

0:       f2 48 0f 2a c7          cvtsi2sd %rdi,  %xmm0
5:       66 48 0f 7e c0          movq     %xmm0, %rax
a:       f3 48 0f b8 c0          popcnt   %rax,  %rax
f:       c3                      retq

Принимает один 64-битный целочисленный параметр в RDI, преобразует его в значение с плавающей запятой в XMM0, сохраняет эти биты обратно RAX, а затем вычисляет вес Хэмминга RAX, оставляя результат, RAXчтобы он мог быть возвращен вызывающей стороне.

Требуется процессор, поддерживающий POPCNTинструкцию, который будет Intel Nehalem, AMD Barcelona и более поздние микроархитектуры.

Для того, чтобы попробовать его в Интернете! , скомпилируйте и запустите следующую программу на C:

#include<stdio.h>
const char g[]="\xF2\x48\x0F\x2A\xC7\x66\x48\x0F\x7E\xC0\xF3\x48\x0F\xB8\xC0\xC3";
#define f(x) ((int(*)(long))g)(x)

int main(int a){
  printf("%d\n",f(22));
  printf("%d\n",f(714));
  printf("%d\n",f(0));
  printf("%d\n",f(1));
  printf("%d\n",f(4503599627370496L));
  printf("%d\n",f(4503599627370495L));
  printf("%d\n",f(1024));
  printf("%d\n",f(-1024));
  printf("%d\n",f(-4096));
  printf("%d\n",f(1000000000));
  printf("%d\n",f(-12345678));
}
ceilingcat
источник
2
+1, правильный инструмент для работы! Это может быть единственный раз, когда x86 может законно конкурировать с языками игры в гольф или победить Jelly. :)
DJMcMayhem
2
Синтаксис AT & T? Вы можете использовать, objdump -drwC -Mintelчтобы разобрать в Intel синтаксис. Если у вас есть указатель в регистре, который вы можете использовать для хранения / перезагрузки, вы можете сохранить байты с помощью movaps [rsi], xmm0/ popcnt rax, [rsi]. (movaps всего 3 байта, на 2 короче, чем movq.) Но это не поможет, потому что [rsp-24]требует 2 дополнительных байта (SIB от использования RSP в качестве основы, плюс disp8). И эти дополнительные байты необходимы как для хранения, так и для перезагрузки. Ну да ладно, я думал, что видел спасение, но нет: /
Питер Кордес
Я сохранил 4 байта с пользовательским соглашением о вызовах . Или все же сохраните 2 байта с тем же соглашением о вызовах, как это, используя инструкции x87.
Питер Кордес
1
@DJMcMayhem: Может быть, не единственный раз. До сих пор нет ответов на языке игры в гольф на задачу Extreme Fibonacci (выведите первые 1000 цифр Fib (1 миллиард) и мой машинный код x86 (105 байтов быстро, или 101 байт, который выполняется за 5 минут вместо 1 минуты) не намного больше, чем некоторые другие ответы, и все они на языках со встроенными целыми числами расширенной точности.
Питер Кордес
2
Или более простая задача (и без требования к производительности), смешивание хроматического ключа с массивом целых чисел . Мой ответ с машинным кодом - половина длины ответа Pyth.
Питер Кордес
11

C (gcc) , 82 68 байт

9 байт благодаря Нейлу.

злой хакинг с плавающей точкой

s;f(long n){double d=n;n=*(long*)&d;for(s=0;n;n*=2)s+=n<0;return s;}

Попробуйте онлайн!

Дрянная Монахиня
источник
Я знал, что ты будешь первым, я просто не ожидал, что язык :-D
Луис Мендо
@ LuisMendo Я просто подумал, что на этом языке было бы удобно ... Я не знаю других языков, которые могли бы это сделать
Leaky Nun
2
Сохраните 9 байтов, сдвинув в другую сторону: ... ;long l=... ;l*=2;)s+=l<0;...
Нил
1
Это, конечно, требует реализации C с 64-битным long. Он работает на x86-64 Linux, но не работает на Windows. Я бы посоветовал сказать «gcc with 64-bit long», поскольку gcc работает на многих платформах, многие из которых имеют разные ABI.
Питер Кордес
1
@ Комментарий Питера - вот почему я добавил «LP64» в редактирование. Я также переставил другой текст в более логичном порядке. Полагаю, вам не понравилось это изменение, и оно откатилось, но LP64 - это стандартный термин, который описывает ABI, где long и указатели являются 64-битными значениями (по сравнению с ILP64, где int также 64-битные, или LLP64, используется в Windows, где только длинные и длинные указатели являются 64-битными, а длинные еще 32-битными). Возможно, мне следовало добавить больше объяснений или встроенную ссылку на соответствующую статью в Википедии.
Коди Грей,
8

Python 3 , 72 71 байт

1 байт благодаря Линн.

lambda n:n and(bin(1020+len(bin(abs(n))))+bin(abs(n))).count('1')-(n>0)

Попробуйте онлайн!

объяснение

Формат binary64 состоит из трех компонентов:

  • первый бит является знаковым битом, 1если число отрицательное
  • следующие 11 бит хранят показатель степени с добавлением 1023
  • следующие 52 бита хранят значение и мантиссу.
Дрянная Монахиня
источник
n and(…)-(n>0)байт короче, нет?
Линн
Или int-> float, или любые другие плавающие, если на то пошло.
user2357112 поддерживает Monica
8

C (gcc) , 47 байтов

f(double n){n=__builtin_popcountl(*(long*)&n);}

Это не портативно; он был протестирован с gcc 7.1.1 на x86_64 под управлением Linux без флагов компилятора.

Попробуйте онлайн!

Деннис
источник
1
Ввод должен быть целым числом. Или можно позволить вызывающей стороне обрабатывать это путем неявного преобразования longв doubleна сайте вызова?
Питер Кордес
1
Кроме того , опираясь на лапе поведения компилятора случиться , чтобы оставить nв raxс ООН-оптимизированный код довольно дрянной. Он ломается, если вы включаете -O3, так что это не просто gcc в общем, это gcc на x86-64 с 64-битной longс отключенной оптимизацией. Если вы включите все эти требования в свой ответ, я бы проголосовал. Я бы предположил, что есть платформы, поддерживаемые gcc, которые имеют 64-битную версию, longно в popcountlрезультате результат остается в регистре, отличном от регистра возвращаемого значения.
Питер Кордес
1
Я взял целое число в математическом смысле. Я добавил спецификации моих тестовых сред, так как не уверен, что достаточно gcc, x86-64 и 64-битных длин. Тем не менее, по крайней мере на x86, функции без возврата работают чаще с gcc (и tcc).
Деннис
Да, я просто перечитал вопрос, и я согласен с тем, что принятие arg в качестве doubleдолжно быть хорошо. В нем ничего не говорится о требовании функции принять ее в формате base2. И да, разные версии gcc могут выдавать разный код, поэтому это тоже важно. (Интересный факт: без -mpopcnt, gcc не будет использовать popcntinsn и будет выдавать последовательность инструкций для эмуляции. Некоторые архитектуры вообще не имеют команды popcnt, поэтому __builtin_popcountlвсегда должны использовать некоторую последовательность insns)
Питер Кордес
Да, многие (большинство?) __builtin_*Функций имеют устаревшие версии, чтобы избежать создания недопустимых инструкций. -march=nativeиспользует popcntqтолько если это доступно.
Деннис
6

C (gcc), 63 байта

f(double d){long s=0,n=*(long*)&d;for(;n;n*=2)s+=n<0;return s;}

Это решение основано на ответе @ LeakyNun, но поскольку он не хочет улучшать свой собственный ответ, я публикую здесь более подходящую версию.

Попробуйте онлайн


источник
2
Я очень сомневаюсь, что никто не хочет улучшить свой ответ.
Мистер Кскодер
1
@ Mr.Xcoder. Хорошо, я буду держать это здесь, пока он не отредактирует свой собственный ответ. Если он не хочет редактировать, он останется здесь. Я опубликовал это улучшение как комментарий к его ответу, и он отклонил его.
1
Я думаю, что ввод должен быть целочисленным типом, а не реальным.
потолок кошка
3
@ThePirateBay Я не видел ваш комментарий к моему ответу, и я до сих пор не вижу его сейчас.
Дрянная Монахиня
9
Решение предложить улучшения или опубликовать свой собственный ответ остается за вами, но вряд ли 6 минут - это около часа .
Деннис
5

C #, 81 70 68 байт

d=>{unsafe{long l=*(long*)&d,s=0;for(;l!=0;l*=2)s-=l>>63;return s;}}

Сохраните 11 байтов благодаря @Leaky Nun.
Сохранено 2 байта благодаря @Neil.

Попробуйте онлайн! Использует System.BitConverter.DoubleToInt64Bitsвместо unsafeкода, так как я не мог заставить TIO работать с ним.

Полная / Отформатированная версия:

namespace System
{
    class P
    {
        static void Main()
        {
            Func<double, long> f = d =>
            {
                unsafe
                {
                    long l = *(long*)&d, s = 0;

                    for (; l != 0; l *= 2)
                        s -= l >> 63;
                    return s;
                }
            };

            Console.WriteLine(f(22));
            Console.WriteLine(f(714));
            Console.WriteLine(f(0));
            Console.WriteLine(f(1));
            Console.WriteLine(f(4503599627370496));
            Console.WriteLine(f(4503599627370495));
            Console.WriteLine(f(1024));
            Console.WriteLine(f(-1024));
            Console.WriteLine(f(-4096));
            Console.WriteLine(f(1000000000));
            Console.WriteLine(f(-12345678));

            Console.ReadLine();
        }
    }
}
TheLethalCoder
источник
for(;l!=0;l*=2)и вам не понадобится троичный
Leaky Nun
@LeakyNun Спасибо, я царапал голову над этим целую вечность.
TheLethalCoder
Вы можете использовать s-=l>>31?
Нил
@ Нил Похоже, не работает. Я полагаю, вы хотите заменить s+=l<0?1:0?
TheLethalCoder
Виноват; lэто долго, так это нужно s-=l>>63?
Нил
4

Python 2 , 69 байт

-12 байт, благодаря @ ASCII-only

lambda n:bin(*unpack('Q',pack('d',n))).count('1')
from struct import*

Попробуйте онлайн!

Мертвый Опоссум
источник
1
71 байт
только ASCII
1
Гольф ваш подход, 76 байт , я рекомендую подход только ASCII
Мистер Xcoder
@ Mr.Xcoder !не нужен, так как порядок байтов здесь не имеет значения
только ASCII
1
69 байтов
только ASCII
@ ASCII-only Упакуйте распакованный. Спасибо: D
Мертвый Опоссум
4

JavaScript (ES6), 81 80 77 байт

f=
n=>new Uint8Array(Float64Array.of(n).buffer).map(g=i=>i&&g(i^i&-i,x++),x=0)|x
<input oninput=o.textContent=f(this.value)><pre id=o>0

Редактировать: 1 байт сохранен благодаря @Arnauld. Сохранено 3 байта благодаря @DocMax.

Нил
источник
Не могли бы вы сделать g(i^i&-i,x++)за -1 байт?
Arnauld
@Arnauld Я действительно задавался вопросом, был ли небольшой бит для игры в гольф, спасибо за то, что нашел это!
Нил
1
-3 больше, если вы замените new Float64Array([n])наFloat64Array.of(n)
DocMax
4

машинный код x86-64, 12 байт для int64_tввода

6 байтов для doubleввода

Требуется popcntрасширение ISA ( CPUID.01H:ECX.POPCNT [Bit 23] = 1).

(Или 13 байтов, если изменение аргумента на месте требует записи всех 64-битных, вместо того, чтобы оставлять мусор в верхних 32-х. Я думаю, что разумно утверждать, что вызывающая сторона, вероятно, в любом случае захочет загрузить только младший 32b, а ноль x86 - расширяется с 32 до 64 неявно с каждой 32-битной операцией. Тем не менее, он останавливает вызывающую функцию add rbx, [rdi]или что-то в этом роде.)

Инструкции x87 короче, чем более очевидный SSE2 cvtsi2sd/ movq(использованный в ответе @ terracecat ), а [reg]режим адресации имеет тот же размер, что и reg: просто байт mod / rm.

Хитрость заключалась в том, чтобы придумать способ передачи значения в памяти без необходимости использовать слишком много байтов для адресации режимов. (например, передача в стек не так уж хороша.) К счастью, правила разрешают чтение / запись аргументов или отдельные выходные аргументы , поэтому я могу просто заставить вызывающую сторону передать мне указатель на память, которую мне разрешено писать.

Вызывается из C с подписью: void popc_double(int64_t *in_out); допустим только младший 32b результата, что может быть странно для C, но естественно для asm. (Для исправления требуется префикс REX в последнем хранилище ( mov [rdi], rax), то есть еще один байт.) В Windows измените rdiна rdx, поскольку Windows не использует x86-64 System V ABI.

Листинг NASM. Ссылка TIO имеет исходный код без разборки.

  1  addr    machine      global popcnt_double_outarg
  2          code         popcnt_double_outarg:
  3                           ;; normal x86-64 ABI, or x32: void pcd(int64_t *in_out)
  4 00000000 DF2F             fild qword  [rdi]    ; int64_t -> st0
  5 00000002 DD1F             fstp qword  [rdi]    ; store binary64, using retval as scratch space.
  6 00000004 F3480FB807       popcnt rax, [rdi]
  7 00000009 8907             mov    [rdi], eax    ; update only the low 32b of the in/out arg
  8 0000000B C3               ret
    # ends at 0x0C = 12 bytes

Попробуйте онлайн! Включает в себя_startтестовую программу, которая передает ему значение и завершается со значением выхода status = popcnt. (Откройте вкладку «отладка», чтобы увидеть его.)

Передача отдельных указателей ввода / вывода также будет работать (rdi и rsi в x86-64 SystemV ABI), но тогда мы не сможем разумно уничтожить 64-битный ввод или так же легко оправдать необходимость 64-битного выходного буфера при записи только низкий 32б.

Если мы хотим утверждать, что мы можем взять указатель на целое число ввода и уничтожить его, возвращая при этом вывод rax, то просто опустить значение mov [rdi], eaxfrom popcnt_double_outarg, уменьшив его до 10 байтов.


Альтернатива без глупых хитростей, 14 байтов

используйте стек как пустое место, pushчтобы получить его там. Используйте push/ popдля копирования регистров в 2 байта вместо 3 для mov rdi, rsp. ( [rsp]всегда требуется SIB-байт, поэтому стоит потратить 2 байта на копирование, rspпрежде чем использовать три инструкции.)

Звоните из C с этой подписью: int popcnt_double_push(int64_t);

 11                               global popcnt_double_push
 12                               popcnt_double_push:
 13 00000040 57                       push   rdi         ; put the input arg on the stack (still in binary integer format)
 14 00000041 54                       push   rsp         ; pushes the old value (rsp updates after the store).
 15 00000042 5A                       pop    rdx         ; mov      rdx, rsp
 16 00000043 DF2A                     fild   qword [rdx]
 17 00000045 DD1A                     fstp   qword [rdx]
 18 00000047 F3480FB802               popcnt rax,  [rdx]
 19 0000004C 5F                       pop    rdi         ; rebalance the stack
 20 0000004D C3                       ret
    next byte is 0x4E, so size = 14 bytes.

Принятие ввода в doubleформате

Вопрос только говорит, что это целое число в определенном диапазоне, а не то, что оно должно быть в двоичном целочисленном представлении base2. Принятие doubleввода означает, что больше нет смысла использовать x87. (Если только вы не используете пользовательское соглашение о вызовах, в котором doubles передается в регистрах x87. Затем сохраните его в красной зоне под стеком и оттуда попкорн.)

11 байт:

 57 00000110 66480F7EC0               movq    rax, xmm0
 58 00000115 F3480FB8C0               popcnt  rax, rax
 59 0000011A C3                       ret

Но мы можем использовать тот же трюк с передачей по ссылке, что и раньше, чтобы сделать 6-байтовую версию: int pcd(const double&d);

 58 00000110 F3480FB807               popcnt  rax, [rdi]
 59 00000115 C3                       ret

6 байт .

Питер Кордес
источник
4

Perl 5 , 33 32 + 1 (-p) = 34 33 байта

Сохранено 1 байт благодаря Hobbs

$_=(unpack"B*",pack d,$_)=~y/1//

Попробуйте онлайн!

Xcali
источник
Вы можете сэкономить 1 байт, сделав dголое слово ( pack d,$_вместо pack"d",$_)
Хоббс
3

MATLAB, 36 байт

@(n)nnz(de2bi(typecast(n,'uint64')))

Использование факта, который de2biне только короче dec2bin, но и дает результат в единицах и нулях, а не ASCII 48, 49.

Sanchises
источник
3

Java (64, 61, 41 байт)

Совершенно просто, используя стандартную библиотеку (Java SE 5+):

int f (long n) {return Long. bitCount (Double. doubleToLongBits (n));}

Вклад Кевина Круйссена (Java SE 5+):

int f(Long n){return n.bitCount(Double.doubleToLongBits(n));}

Вклад Кевина Круйссена (Java SE 8+, лямбда-функция):

n->n.bitCount(Double.doubleToLongBits(n))
Nayuki
источник
Красиво сделано! :-)
Дрянная Монахиня
1
Хороший ответ, +1 от меня. Вы можете сыграть в гольф три байта, взяв параметр as Long nи используя n.bitCount(...)вместо Long.bitCount(...). Кроме того, если вы используете Java 8+, вы можете n->n.bitCount(Double.doubleToLongBits(n))
Кевин Круйссен,
2

Просто чтобы попробовать другой, более безопасный, чем TheLethalCoder подход, я придумал это (жаль, что C # имеет такие длинные имена методов):

C # (.NET Core) , 76 + 13 байт

d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Split('1').Length-1

Попробуйте онлайн!

Количество байтов включает 13 байтов для using System;. Сначала мне нужно преобразовать в doublea, longкоторый имеет такое же двоичное представление, затем я могу преобразовать его в двоичный файл string, а затем я посчитал 1s, просто разделив строку и посчитав подстроки минус 1.

Чарли
источник
Хорошая альтернатива, но вы должны включить usingв свой счетчик байтов.
TheLethalCoder
Использование Linq для 95 байт только несколько: namespace System.Linq;{d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Count(c=>c>48)}. Хотя я не проверял это, оно должно работать.
TheLethalCoder
@TheLethalCoder работает, но я старался избегать Linq, поэтому мне не пришлось добавлять вторую usingдирективу.
Чарли
1
Когда вы добавляете второе, это когда namespaceпригодится. Но да, в этом случае избежать Linq было немного дешевле. Я просто хотел прокомментировать этот подход, если у вас есть идеи, как сократить его, чтобы сэкономить байты.
TheLethalCoder
@TheLethalCoder, Sum(c=>c&1)короче. ИлиSum()-768
Питер Тейлор
1

постоянный ток, 79 байт

[pq]su[-1r]st0dsb?dd0=u0>tsa[1+]ss[la2%1=slb1+sblad2/sa1<r]dsrxlb1022+sa0lrx+1-

Выход остается на вершине стека.
Я добавлю объяснение позже.

Попробуйте онлайн!

Обратите внимание, что отрицательным числам предшествует _, а не -.

poi830
источник
1

C 67 байт

int i;g(char*v){int j=v[i/8]&1<<i%8;return!!j+(++i<64?g(v):(i=0));}

контрольный код и результаты

#define R     return
#define u32 unsigned
#define F        for
#define P     printf

int main()
{/*           5   6 0 10                5               55    3      4       16*/
 double v[]={22,714,0,1 ,4503599627370496,4503599627370495,1024, -1024, -12345678};
 int i; 

 F(i=0;i<9;++i)
     P("%f = %d\n", v[i], g(&v[i]));
 R 0;
}

>tri4
22.000000 = 5
714.000000 = 6
0.000000 = 0
1.000000 = 10
4503599627370496.000000 = 5
4503599627370495.000000 = 55
1024.000000 = 3
-1024.000000 = 4
-12345678.000000 = 16
RosLuP
источник