Средние биты: средний вызов

30

Учитывая целое число N> = 1, выведите среднее число битов в целое число от 0 до N - 1

Спецификация

  • Выходные данные могут быть рассчитаны как сумма количества битов в двоичном представлении каждого целого числа от 0 до N-1, деленная на N.
  • В этом контексте двоичное представление целого числа не имеет ведущих нулей, за исключением нуля, который представлен как 0 в двоичном виде.
  • Вывод должен быть точным как минимум до 7 значащих цифр.

пример

N = 6

0: 0   : 1 bit
1: 1   : 1 bit
2: 10  : 2 bits
3: 11  : 2 bits
4: 100 : 3 bits
5: 101 : 3 bits

Среднее количество битов = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

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

Вход => выход

1 => 1
2 => 1
3 => 1.3333333
4 => 1.5
5 => 1.8
6 => 2
7 => 2.1428571

Фрагмент таблицы лидеров

( отсюда )

Показать фрагмент кода

Обратите внимание, что сумма (до деления, чтобы найти среднее) является последовательностью в OEIS .

code-golf math binary bitwise statistics Trichoplax
источник
6
Хорошее имя, очень маленькое .
R
3
Для тех, кто не знает, я с большей вероятностью опишу решения с объяснением
trichoplax
4
Недостаточно каламбур, вам нужно немного больше, чтобы это было идеально.
clismique
1
Я предполагаю, что под "каждым числом" вы подразумеваете "каждое целое число "?
Cyoce
@ Да, спасибо, что указали на это - я отредактировал, чтобы уточнить.
Трихоплакс

Ответы:

13

Pyth, 6 байт

.Oml.B

Попробуйте это онлайн здесь .

.Oml.BdUQ              Filling in implict vars

.O                     Average of list
 m   UQ                Map over [0..input)
  l                    Length of
   .B                  Binary string representation of int
    d                  Lambda var
Maltysen
источник
Совместное первое место, но вы не появлялись в списке лидеров - я внес небольшое изменение в заголовок, чтобы исправить это.
трихоплакс
9

Желе, 6 байт

R’BFL÷

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

R’BFL÷  Main monadic chain. Argument: n

R       yield [1, 2, ..., n]
 ’      decrement; yield [0, 1, ..., n-1]
  B     convert to binary; yield [[0], [1], [1,0], [1,1], ...]
   F    flatten list; yield [0, 1, 1, 0, 1, 1, ...]
    L   length of list
     ÷  divide [by n]
Дрянная Монахиня
источник
7

Октава, 29 байт

@(n)1+sum(fix(log2(1:n-1)))/n

объяснение

              log2(1:n-1)       % log2 of numbers in range [1..n-1]
                                % why no 0? because log2(0) = -Inf  :/
          fix(           )      % floor (more or less, for positive numbers)
      sum(                )     % sum... wait, didn't we miss a +1 somewhere?
                                % and what about that missing 0?
                           /n   % divide by n for the mean
    1+                          % and add (1/n) for each of the n bit lengths 
                                % (including 0!)

Пробный прогон на идеоне .

мерный стакан
источник
6

Python 3, 43 байта

def f(n):x=len(bin(n))-2;return(2-2**x)/n+x

Использует формулу на странице OEIS . Удивительно, но именованная функция здесь как-то дешевле из-за присвоенияx .

Альтернативный подход для 46 байтов:

lambda n:-~sum(map(int.bit_length,range(n)))/n

К сожалению, -~это необходимо , так как (0).bit_length()это 0, но даже тогда это было бы слишком долго байт.

Sp3000
источник
6

Юлия, 27 байт

n->endof(prod(bin,0:n-1))/n

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

Как это работает

Поскольку *в Julia prodиспользуется конкатенация строк, ее можно использовать для конкатенации массива строк. При желании он принимает функцию в качестве первого аргумента, который сопоставляется со вторым, перед тем, как взять фактический «продукт», так же prod(bin,0:n-1)как и строка двоичного представления всех целых чисел в требуемом диапазоне. Взятие длины с endofделением на n дает среднее значение.

Деннис
источник
5

Юлия, 28 байт

n->mean(ceil(log2([2;2:n])))

Так binкак автоматически не отображает массивы, мы используем, ceil(log2(n))чтобы получить количество бит в n-1. Это хорошо работает, потому что a:bнотация Джулии включает оба конца, так 2:nже как и диапазон от 2 до n, но мы действительно рассчитываем количество бит для чисел в диапазоне 1:n-1. К сожалению, нам нужно добавить еще, 2чтобы учесть 0.

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

Sp3000
источник
5

MATL, 9 байт

q:ZlksG/Q

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

Модифицированная версия со всеми тестами

объяснение

    % Implicitly grab input (N)
q:  % Create array from 1:N-1
Zl  % Compute log2 for each element of the array
k   % Round down to the nearest integer
s   % Sum all values in the array
G   % Explicitly grab input again
/   % Divide by the input
Q   % Add 1 to account for 0 in [0, ... N - 1]
    % Implicitly display the result
Suever
источник
Щелчок!! (наполнитель)
Дэвид
@ Дэвид На самом деле, ты был прав. Дублирование ввода в начале не работает для других значений ... вам нужно G/Qв конце.
стакан
5

MATL, 9 байт

:qBYszQG/

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

объяснение

:qBYszQG/
:               % take vector [1..n]
 q              % decrement by 1 to get [0..n-1]
  B             % convert from decimal to binary
   Ys           % cumulative sum (fills in 0's after first 1)
     z          % number of nonzero elements
      Q         % increment by 1 to account for zero
       G        % paste original input (n)
        /       % divide for the mean
мерный стакан
источник
5

Желе, 8 байт

Не короче, но интересный алгоритм и моя первая подача желе:

Rl2Ċ»1S÷

R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
Адам
источник
4

Желе, 10 байт

BL©2*2_÷+®

Из предложения Sp3000.

Попробуй это здесь.

Желе, 11 байт

æḟ2’Ḥ÷_BL$N

Не очень коротко, но мне нужно несколько советов.

Попробуй это здесь.

Используя ту же формулу, что и в ответе Sp3000 . (Это не очень сложно получить самостоятельно, дифференцируя геометрическую прогрессию.)

jimmy23013
источник
Посмотрите на мой ответ желе для вашей справки.
Утренняя монахиня
@LeakyNun Использует другой подход, который, я не думаю, будет короче вашего. Но _BL$Nказалось, довольно долго ...
jimmy23013
Таким образом, в основном, ваш код «пол до ближайшей степени 2, минус 1, двойной, делить на вход, минус двоичная длина ввода, отрицательный»?
Утренняя монахиня
@LeakyNun Да ..
jimmy23013
3
Только незначительно лучше:BL©2*2_÷+®
Sp3000
4

Java, 135 95 90 байт

float a(int n){int i=0,t=0;for(;i<n;)t+=Integer.toString(i++,2).length();return t/(n+0f);}
Шон Уайлд
источник
Я думаю, что вы можете избавиться от интерфейса и просто создать функцию или лямбду. Также вы можете вернуть значение вместо вывода его на стандартный вывод.
Frozn
Хорошо, я перейду с этими правилами.
Шон Уайлд
Я думаю, что это должно быть разрешено. Поскольку в OP ничего не указано, я думаю, что применяются стандартные правила ввода / вывода .
Frozn
Да, функция в порядке - вам не нужна полная программа. Обратите внимание, что таблица лидеров поднимает счет в первой строке, поэтому ваш счет в настоящее время отображается как 135 вместо 95.
trichoplax
@trichoplax Еще последнее место. Я виню Яву лично ...
Шон Уайлд
3

Python 3, 46 байт

lambda x:sum(len(bin(i))-2for i in range(x))/x

Назови это как

f = lambda x: sum(len(bin(i))-2for i in range(x))/x
print(f(6))
# 2.0

Я должен был отменить ревизию карты, потому что не удалось ввести 5

Keatinge
источник
3

05AB1E, 9 7 байт

Код:

L<bJg¹/

Объяснение:

L<         # range from 0..input-1
  b        # convert numbers to binary
   J       # join list of binary numbers into a string
    g      # get length of string (number of bits)
     ¹/    # divide by input

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

Редактировать: сохранено 2 байта благодаря @Adnan

Emigna
источник
@Adnan: Спасибо! Забыл о Дж.
Эминья
3

C #, 87 байт

double f(int n){return Enumerable.Range(0,n).Average(i=>Convert.ToString(i,2).Length);}

Я написал ответ на C #, потому что я его не видел. Это мой первый пост к одному из них, поэтому, пожалуйста, дайте мне знать, если я делаю что-то не так.

raive
источник
Добро пожаловать в Программирование головоломок и Code Golf. Это отличный первый ответ, +1. Можете ли вы перейти doubleна floatсохранение одного байта или вам нужна точность?
wizzwizz4
2
@ wizzwizz4 Спасибо! У меня была такая же мысль, но Average () возвращает двойной. Если я изменяю свой тип возвращаемого значения на float, то я должен явно разыграть double и получить 7 байтов.
Рейв
2

JavaScript (ES7), 38 32 байта

n=>(l=-~Math.log2(n))-(2**l-2)/n

Использование формулы @ sp3000 (предыдущая версия была рекурсивным решением). Версия ES6 для 34 байтов:

n=>(l=-~Math.log2(n))-((1<<l)-2)/n

Пояснение формулы: рассмотрим случай N = 55. Если мы напишем двоичные числа (вертикально, чтобы сэкономить место), мы получим:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

Размер этого прямоугольника равен nl, поэтому среднее значение равно l, но нам нужно исключить пробелы. Каждый ряд заготовок в два раза длиннее предыдущего, поэтому общая сумма составляет 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 л - 2.

Нил
источник
2

J, 21 17 15 байт

Благодаря 17 байтам до 15 байт благодаря @Dennis.

+/@:%~#@#:"0@i.

Кто-нибудь может помочь мне в этом?

Неуправляемая версия

range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
Дрянная Монахиня
источник
Я попробовал альтернативный подход, по stringifying списка двоичных цифр, и вышел с 25 байтами: %~>:@#@([:":10#.[:#:i.)-]. Ваше решение выглядит довольно оптимальным.
Конор О'Брайен
2

Perl 6 ,  34  32 байта

{$_ R/[+] map *.base(2).chars,^$_}

{$_ R/[+] map {(.msb||0)+1},^$_}

Объяснение:

{ 
  $_  # the input
  R/  # divides ( ｢$a R/ $b｣ is the same as ｢$b / $a｣ )
  [+] # the sum of:
  map
    {
      (
       .msb # the most significant digit (0 based)
       || 0 # which returns Nil for ｢0.msb｣ so use 0 instead
            # should be ｢(.msb//0)｣ but the highlighting gets it wrong
            # it still works because it has the same end result 
      ) 
      + 1   # make it 1 based
    },
    ^$_ # ｢0 ..^ $_｣ all the numbers up to the input, excluding the input
}

Тест:

use v6.c;

# give it a name
my &mean-bits = {$_ R/[+] map {(.msb||0)+1},^$_}

for 1..7 {
  say .&mean-bits
}

say '';

say mean-bits(7).perl;
say mean-bits(7).base-repeating(10);
1
1
1.333333
1.5
1.8
2
2.142857

<15/7>
(2. 142857)
Брэд Гилберт b2gills
источник
2

Dyalog APL , 14 байтов

(+/1⌈(⌈2⍟⍳))÷⊢

range ← ⍳
log   ← ⍟
log2  ← 2 log range
ceil  ← ⌈
bits  ← ceil log2
max   ← ⌈
fix0  ← 1 max bits
sum   ← +/
total ← sum fix0
self  ← ⊢
div   ← ÷
mean  ← sum div self
Адам
источник
2

Clojure, 71 64 63 байта

Похоже, что отношения в порядке, в соответствии с какими числовыми форматами приемлемы в выводе

(fn[n](/(inc(apply +(map #(.bitLength(bigint %))(range n))))n))

  • n = 1 => 1
  • n = 7 => 15/7

ungolfed (и немного переписан для простоты объяснения)

(fn [n]
 (->
  (->>
   (range n)                      ;;Get numbers from 0 to N
   (map #(.bitLength (bigint %))) ;;Cast numbers to BigInt so bitLength can be used
   (apply +)                      ;;Sum the results of the mapping
   (inc))                         ;;Increment by 1 since bitLength of 0 is 0
  (/ n)))                         ;;Divide the sum by N

старый ответ, который использовал (float):

(fn[n](float(/(inc(apply +(map #(..(bigint %)bitLength)(range n))))n)))

вывод похож на:

  • n = 1 => 1,0
  • n = 7 => 2,142857
отметка
источник
Вопрос о приемлемости дробей или соотношений ранее не поднимался. Для этого испытания я приму любой достигнутый консенсус относительно того, каким должен быть дефолт .
трихоплакс
1

Минколанг 0,15 , 23 байта

n$z1z[i1+2l$M$Y+]kz$:N.

Попробуй это здесь!

объяснение

n$z                       Take number from input and store it in register (n)
   1                      Push 1 onto the stack
    z[                    For loop that repeats n times
      i1+                 Loop counter + 1
         2l$M             log_2
             $Y           Ceiling
               +          Add top two elements of stack
                ]         Close for loop
                 z$:      Float divide by n
                    N.    Output as number and stop.

Довольно простая реализация.

El'ndia Starman
источник
1

JavaScript ES5, 55 байт

n=>eval(`for(o=0,p=n;n--;o+=n.toString(2).length/p);o`)

объяснение

n =>   // anonymous function w/ arg `n`
  for( // loop
      o=0,  // initalize bit counter to zero
      p=n   // copy the input
    ;n-- // will decrease input every iteration, will decrease until it's zero
    ;o+=    // add to the bitcounter
        n.toString(2)  // the binary representation of the current itearations's
                     .length // length
        /p   // divided by input copy (to avergage)
   );o       // return o variable
Downgoat
источник
1

Хун , 71 байт

|=
r/@
(^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq

... Я уверен, что это первый раз, когда я использовал ядра с плавающей запятой от Хуна. Это на самом деле реализация, написанная на Hoon, которая отправляется в SoftFloat, поскольку единственными типами данных в Hoon являются атомы и ячейки.

Создать функцию, которая принимает атом r. Создайте список из [0 .. (r - 1)], отобразите список, взяв двоичный логарифм числа, затем сверните этот список с помощью ++add. Преобразовать как выход из сгиба и rв@rq (числа с плавающей запятой с четверной точностью) с++sun:rq , а затем разделите одно на другое.

Самое странное в этом фрагменте - :.^rqконец. a:bв Хуне означает «оценить А в контексте б». ++rqэто ядро, которое содержит всю реализацию с четверной точностью, например, библиотеку. Так работает(sun 5):rq - это то же самое, что и(sun:rq 5) .

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

При оценке выражения в контексте компилятор ищет глубину лимба в первую очередь. В нашем случае a:[. rq]это будет выглядеть во всем текущем контексте, aпрежде чем перейти к поиску rq. Так что addбудет искать функцию, которая работает на атомах вместо чисел с плавающей точкой ... но так будет div. Hoon также имеет функцию, где использование^name будет игнорировать первую найденную ссылку и искать вторую.

После этого он просто использует синтетический сахар a^b, равный равенству, чтобы [a b]оценить наш фрагмент как с нашим текущим контекстом, так и с плавающей библиотекой с четверной точностью, игнорируя атомарный div в пользу ++div:rq.

> %.  7
  |=
  r/@
  (^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
.~~~2.1428571428571428571428571428571428
RenderSettings
источник
1

На самом деле 7 байтов:

;r♂├Σl/

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

Объяснение:

;r♂├Σl/
;        duplicate input
 r       push range(0, n) ([0, n-1])
  ♂├     map binary representation
    Σ    sum (concatenate strings)
     l/  divide length of string (total # of bits) by n

Если бы не ошибка, которую я только что обнаружил, это решение работало бы для 6 байтов:

r♂├♂læ

æ это встроенная средняя команда.

Mego
источник
Разве это не 10 байтов? Я проверил на bytesizematters.com.
m654
1
@ m654 На самом деле не использует UTF-8, он использует CP437 (или что-то в этом роде).
Алекс А.
@AlexA. О, не знал этого.
m654
1
@ m654 Bytesizematters использует полностью составленную кодировку, которая не существует (и не может быть ) на практике. Для UTF-8 используйте mothereff.in/byte-counter .
Деннис
@ Денис Спасибо за информацию, я буду иметь это в виду.
m654
1

Витси, 26 байт

Это первая попытка, я добавлю к этому больше информации и позже добавлю объяснение.

0vVV1HV1-\[2L_1+v+v]v1+V/N

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

Аддисон Крамп
источник
1

PowerShell v2 +, 64 байта

param($n)0..($n-1)|%{$o+=[convert]::ToString($_,2).Length};$o/$n

Очень простая реализация спецификации. Петли от 0до $n-1с |%{...}. Каждая итерация, мы [convert]наш номер входа $_в строке базу 2и занять его length. Мы накапливаем это в $o. После петель мы просто делим$o/$n , оставляя это на конвейере, и вывод неявен.

Пока это так, это на самом деле короче, чем формула, которую используют Sp и другие, так как [math]::Ceiling()и [math]::Log()смехотворно многословны. Базовое преобразование в PowerShell - отвратительно.

AdmBorkBork
источник
1

Perl 5,10, 54 байта

for(1..<>){$u+=length sprintf"%b",$_;$n++}$u/=$n;say$u

Довольно просто. sprintf"%b"это аккуратный способ вывода числа в двоичном виде в Perl без использования дополнительных библиотек.

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

Пол Пикард
источник
1

CJam, 13 12 11 байтов

Один байт сохранен благодаря @ Sp3000, а другой благодаря @ jimmy23013

rd_,2fbs,\/

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

объяснение

Непосредственная. Применяет определение.

rd      e# read input and convert to double 
_       e# duplicate 
,       e# range from 0 to input minus 1
2fb     e# convert each element of the array to binary 
s       e# convert to string. This flattens the array
,       e# length of array 
\       e# swap 
/       e# divide
Луис Мендо
источник
1

Джольф, 10 байт

/uΜr0xdlBH

Попробуй это здесь!

объяснение

/uΜr0xdlBH
  Μr0x      map range 0..x
      dlBH  over lengths of binary elements
/u          divide sum of this
            by implicit input (x)
Конор О'Брайен
источник
1

Swift, 72 байта

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
Джон МакДауэлл
источник
2
Вам не нужно вызывать функцию, оставив ее как определенную функцию. Хороший первый пост.
R
1

J 15 байт

%~[:+/#@#:"0@i.

Это монадический глагол, используемый следующим образом:

   f =: %~[:+/#@#:"0@i.
   f 7
2.14286

Попробуй это здесь!

объяснение

Я реализовал спецификацию задачи в буквальном смысле. Есть и другие подходы, но все оказалось дольше.

%~[:+/#@#:"0@i.  Input is y
             i.  Range from 0 to y-1.
          "0@    For each number in this range:
      #@           Compute the length of
        #:         its base-2 representation.
  [:+/           Take the sum of the lengths, and
%~               divide by y.
Zgarb
источник