считать в диапазоне

20

Вызов :

Подсчитайте количество единиц 1в двоичном представлении всех чисел в диапазоне.

Вход:

Два недесятичных натуральных числа

Выход :

Сумма всех 1s в диапазоне между двумя числами.

Пример :

4 , 7        ---> 8
4  = 100 (adds one)   = 1
5  = 101 (adds two)   = 3
6  = 110 (adds two)   = 5
7  = 111 (adds three) = 8

10 , 20     ---> 27
100 , 200   ---> 419
1 , 3       ---> 4
1 , 2       ---> 2
1000, 2000  ---> 5938

Я объяснил только первый пример, иначе он занял бы огромное количество места, если бы я попытался объяснить для всех них.

Замечания :

  • Числа могут быть разделены более чем на 1000
  • Все входные данные будут действительными.
  • Минимальный выход будет один.
  • Вы можете принять число в виде массива из двух элементов.
  • Вы можете выбрать порядок номеров.

Критерии победы:

Это код-гольф, поэтому выигрывает самый короткий код в байтах для каждого языка.

code-golf math number binary Мухаммед Салман
источник
1
OEIS A000788
монахиня
1
Можем ли мы принять входные данные как некоторый тип диапазона ( IntRangeв Kotlin, Rangeв Ruby)?
улитка_
Интересный факт: случай 1000 - 2000дает 5938, но опустить случай на 1000, то результат также снижается на 1000: 0-1000 = 4938. доказательство
steenbergh

Ответы:

9

JavaScript (ES6), 38 байт

Принимает ввод в синтаксис карри (a)(b).

a=>b=>(g=c=>a>b?0:1+g(c^c&-c||++a))(a)

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

комментарии

a => b => (         // given the input values a and b
  g = c =>          // g = recursive function taking c = current value
    a > b ?         // if a is greater than b:
      0             //   stop recursion and return 0
    :               // else:
      1 +           //   add 1 to the final result
      g(            //   and do a recursive call to g() with:
        c ^ c & -c  //     the current value with the least significant bit thrown away
        || ++a      //     or the next value in the range if the above result is 0
      )             //   end of recursive call
)(a)                // initial call to g() with c = a
Arnauld
источник
5

Ява (JDK 10) , 55 байт

a->b->{int c=0;for(;a<=b;)c+=a.bitCount(b--);return c;}

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

Оливье Грегуар
источник
IntStream.range(a,b+1).map(Integer::bitCount).sum()
saka1029
@ saka1029 Импорт обязателен. Так что на самом деле a->b->java.util.stream.IntStream.range(a,b+1).map(Integer::bitCount).sum(), на целых 74 байта. Даже если импорт не был обязательным, параметры есть, поэтому мы должны были бы написать a->b->IntStream.range(a,b+1).map(Integer::bitCount).sum(), что считается 57 байтами
Оливье Грегуар
Вы также можете получить a->b->IntStream.range(a,b+1).map(Long::bitCount).sum()улучшение на 1 байт. Маргинальный, но все же один.
NotBaal
@NotBaal Как упоминал Оливье в комментарии выше, импорт является обязательным, поэтому он должен быть a->b->java.util.stream.IntStream.range(a,b+1).map(Long::bitCount).sum()(71 байт).
Кевин Круйссен
4

MATL , 5 4 байта

&:Bz

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

Спасибо Луису Мендо за сохранение байта!

(implicit input a and b, a<b)
&:                              % two-element input range, construct [a..b]
  B                             % convert to Binary as a logical vector (matrix)
   z                            % number of nonzero entries
(implicit output of the result)

Giuseppe
источник
4

R , 41 34 байта

function(a,b)sum(intToBits(a:b)>0)

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

Сильно вдохновлен другим решением R от ngm . Это использует другой подход после преобразования в биты. Огромное спасибо Джузеппе за подсказку о возможном решении 34 байта.

Jayce
источник
34 байта возможно! Я забыл, где я видел трюк (я знаю, что не придумал его), но есть более хитрое преобразование в sumвектор mable - я опубликую, если вы / ngm не можете его найти.
Джузеппе
@Giuseppe Действительно!
JayCe
2
Я сократил его до 37 байт, используя технику, которая в противном случае могла бы быть полезной. Также обнаружил, что sdи varпринуждать все, что они могут удвоить.
НГМЫ
Вы можете использовать pryr::fдля сохранения 4 байта: tio.run/##K/qfZvu/…
pajonk
@pajonk хорошая мысль! Но я пытаюсь придерживаться базовых пакетов R, а не R + Pryr. Я собираюсь искать на мета то, что можно считать «чистым R».
JayCe
3

Желе , 4 байта

rBFS

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

объяснение

rBFS - Полная программа. Принимает два входа из аргументов командной строки.
r - дальность
 B - Для каждого конвертировать в двоичный файл.
  ПС - Свести и суммировать.
Мистер Xcoder
источник
О_о, это было быстро?
Мухаммед Салман
@MuhammadSalman Ну, проблема также вроде тривиального ИМО.
Мистер Кскодер
Это может быть, но ответ через минуту после публикации.
Мухаммед Салман
1
@MuhammadSalman Да, это не так быстро для таких простых задач, как этот; знание желе также вытекает. Реальные усилия идут, например, на языке этого месяца, QBasic. ;-)
Эрик Outgolfer
@EriktheOutgolfer: Можете ли вы ответить на этот вопрос в QBasic / BrainF ** k?
Мухаммед Салман
3

Python 3 , 56 54 52 байта

Это может быть игра в гольф больше IMO. -2 байта благодаря Mr.Xcoder -2 Больше байтов благодаря MI Wright

lambda a,b:''.join(map(bin,range(a,b+1))).count('1')

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

Печенье мельницы
источник
2

Баш + коммунальные услуги, 50

jot -w%o - $@|tr 247356 1132|fold -1|paste -sd+|bc

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

Преобразование целых чисел в двоичные строки всегда немного затрудняет работу bash. Подход здесь немного другой - преобразуйте целые числа в восьмеричные, затем замените каждую восьмеричную цифру числом двоичных 1, которые в ней содержатся. Тогда мы можем просто сложить все преобразованные цифры

Цифровая травма
источник
2

APL + WIN, 33 26 байт

Запрашивает вектор целых чисел:

+/,((↑v)⍴2)⊤(1↓v)+0,⍳-/v←⎕

Попробуйте онлайн! Предоставлено Dalog Classic

Объяснение:

v←⎕ prompt for input of a vector of two integers max first

(v←1↓v)+0,⍳-/ create a vector of integers from min to max

(↑v)⍴2 set max power of 2 to max 

⊤ convert integers to a matrix of binaries

+/, convert matrix to a vector and sum
Грэхем
источник
2

Октава с инструментарием связи, 21 байт

@(a,b)nnz(de2bi(a:b))

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

Код должен быть довольно очевидным. Количество ненулевых элементов в двоичном представлении каждого из чисел в диапазоне.

Это было бы @(a,b)nnz(dec2bin(a:b)-48)без инструментов коммуникации.

Стьюи Гриффин
источник
1

PHP, 97 байт

(конечно, это можно сократить, но хотел использовать функции)

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

Код

<?=substr_count(implode(array_map(function($v){return decbin($v);},
 range($argv[0],$argv[1]))),1);

объяснение

<?=
 substr_count(   //Implode the array and count every "1"
  implode(
    array_map(function($v){return decbin($v);}, //Transform every decimal to bin
          range($argv[0],$argv[1])   //generate a range between the arguments
     )
),1);   //count "1"'s
Франциско Хан
источник
кажется, вы можете просто сделать это
dzaima
На секунду я абсолютно забыл, что вы можете установить имя функции php непосредственно в качестве параметра :-(
Francisco Hahn
$argv[0]название программы или "-"; Вы должны работать с $argv[1]и $argv[2]. И вы можете использовать joinвместо implode, сокращая это до 68 байтов:<?=substr_count(join(array_map(decbin,range($argv[1],$argv[2]))),1);
Тит
1

PowerShell , 72 байта

param($x,$y)$x..$y|%{$o+=([convert]::ToString($_,2)-replace0).length};$o

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

Долго из-за преобразования в двоичный код [convert]::ToString($_,2)и избавления от нулей -replace0. В противном случае мы просто берем входные числа, создаем диапазон $x..$yи для каждого числа в диапазоне преобразуем его в двоичный, удаляем нули, берем .lengthих (т. Е. Количество оставшихся единиц) и добавляем их в наш $output.

AdmBorkBork
источник
попробуйте countвместо этого length:)
mazzy
1
@mazzy countвсегда будет, 1потому что мы считаем lengthстроку, а не массив.
AdmBorkBork
строка! вы правы. Благодарю. -replace0умный
Маззи
1

Пип , 10 байт

$+JTB:a\,b

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

объяснение

            a and b are command-line args (implicit)
      a\,b  Inclusive range from a to b
   TB:      Convert to binary (: forces TB's precedence down)
  J         Join into a single string of 1's and 0's
$+          Sum (fold on +)
DLosc
источник
1

Брахилог , 8 байт

⟦₂ḃᵐcọht

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

объяснение

⟦₂         Ascending range between the two elements in the input
  ḃᵐ       Map to base 2
    c      Concatenate
     ọ     Occurrences of each element
      h    Head: take the list [1, <number of occurrences of 1>]
       t   Tail: the number of occurrences of 1
Fatalize
источник
1

K (нгн / к) , 19 13 байт

{+//2\x_!1+y}

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

{ }это функция с аргументами xиy

!1+y список 0 1 ... у

x_ отбрасывает первые х элементов

2\ кодирует каждое целое как список двоичных цифр одинаковой длины (это специфично для ngn / k)

+/ сумма

+//сумма до схождения; в этом случае сумма суммы всех двоичных списков цифр

СПП
источник
1

Perl 6 , 32 30 байт

-1 байт благодаря Брэду Гилберту

{[…](@_)>>.base(2).comb.sum}

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

Объяснение:

[…](@_)    #Range of parameter 1 to parameter 2
       >>    #Map each number to
                      .sum  #The sum of
                 .comb      #The string of
         .base(2)    #The binary form of the number
Джо Кинг
источник
1
Вы можете уменьшить его на один байт, если используете [...](@_)вместо этого($^a..$^b)
Брэд Гилберт b2gills
1

J , 16, 15 14 байтов

1 байт сохранен благодаря FrownyFrog!

+/@,@#:@}.i.,]

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

Объяснение:

Диадический глагол, левый аргумент - нижняя граница mдиапазона, правый - верхний n.

            ,    append                      
             ]   n to the
          i.     list 0..n-1
         }.      drop m elements from the beginning of that list 
      #:@        and convert each element to binary 
    ,@           and flatten the table
 +/@             and find the sum
Гален Иванов
источник
Вы можете сделать это 14?
FrownyFrog
@FrownyFrog Попробую сегодня попозже (видимо это возможно, так как вы спрашиваете :))
Гален Иванов
@FrownyFrog 15 пока, я все еще пытаюсь ...
Гален Иванов
1
14
FrownyFrog
@FrownyFrog Ааа, так просто! Я думал о, }.но всегда в вилке, а не в крючке. Благодарность!
Гален Иванов
1

QBasic, 95 93 83 82 байта

@DLosc спас мне немного много байт!

Сохраненный другой байт, используя эту технику !

INPUT a,b
FOR i=a TO b
k=i
FOR j=i TO 0STEP-1
x=k>=2^j
s=s-x
k=k+x*2^j
NEXT j,i
?s

Язык месяца FTW!

объяснение

INPUT a,b           Ask user for lower and upper bound
FOR i=a TO b        Loop through that range
k=i                 we need a copy of i to not break the FOR loop
FOR j=i TO 0STEP-1  We're gonna loop through exponents of 2 from high to low.
                    Setting the first test up for 4 to 2^4 (etc) we know we're overshooting, but that 's OK
x=k>=2^j            Test if the current power of 2 is equal to or smaller than k 
                    (yields 0 for false and -1 for true)
s=s-x               If k is bigger than 2^j, we found a 1, so add 1 to our running total s
                    (or sub -1 from the total s...)
k=k+x*2^j           Lower k by that factor of 2 if the test is true, else by 0
NEXT                Test the next exponent of 2
NEXT                process the next number in range
?s                  print the total

Последний тестовый сценарий от 1000 до 2000 действительно работает, в QBasic 4.5, работающем на Dosbox: Хидеет хет!

steenbergh
источник