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

Это довольно многословное объяснение - поэтому давайте разберем его с проработанным примером.

Для этого примера мы будем использовать число 3167. В двоичном виде это:

110001011111

(Обратите внимание, что во время преобразования в двоичный файл вы должны убрать начальные нули)

Он не начинается и не заканчивается 0, поэтому мы удаляем 1 пару битов:

1  1000101111  1

И другой:

11  00010111  11

Но теперь в начале есть 0, поэтому мы не можем больше удалять 1пары. Всего мы удалили 4 бита, и поэтому 4 - это цифровая жесткость 3167.

Однако для чисел, которые можно записать как 2 ⁿ -1 для положительного n (то есть содержать только 1в двоичном представлении), 0 никогда не будет достигнуто, и поэтому все биты могут быть удалены. Это означает, что твердость - это просто длина целого бита.

Соревнование

Ваша задача - написать программу или функцию, которая, учитывая неотрицательное целое число n >= 0, определяет его цифровую твердость.

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

Тестовые случаи

Пожалуйста, сообщите мне, если какой-либо из них является неправильным, или если вы хотите предложить какие-либо крайние случаи для добавления.

0     -> 0
1     -> 1
8     -> 0
23    -> 2
31    -> 5
103   -> 4
127   -> 7
1877  -> 2
2015  -> 10

Вот отличное решение Python, которое я использовал для генерации этих тестовых случаев (не гарантировано, что они не содержат ошибок):

def hardness(num) -> int:
    binary = bin(num)[2:]

    if binary.count('0') == 0:
        return num.bit_length()

    revbin = binary[::-1]

    return min(revbin.find('0'), binary.find('0')) * 2

Желе , 11 10 байт

BµQL××Ṛa\S

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

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

BµQL××Ṛa\S  Main link. Argument: n

B           Binary; convert n to base 2.
 µ          Begin a new, monadic chain. Argument: A (array of binary digits)
  Q         Unique; deduplicate the digits.
   L        Length; count the unique digits.
    ×       Multiply each digit by the result.
     ×Ṛ     Multiply the results by reversed A.
       a\   Cumulative reduce by logical AND.
            This zeroes out all elements after the first zero.
         S  Compute the sum of the result.

Python , 76 69 68 63 62 60 57 байт

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

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

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

Это рекурсивное решение, которое принимает вход n и продолжает увеличивать k - начиная с 0 - в то время как LSB _k (n) (бит с индексом k справа) и MSB _k (n) (бит с индексом k слева) установлены. По окончании возвращает k, если все биты n установлены, и 2k, если нет.

Давайте начнем с переписывания лямбда- функции f как именованной функции F со вспомогательной переменной t .

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

В каждом вызове F мы сначала сдвигаем бит n всего на k единиц вправо и сохраняем результат в t . Таким образом, LSB ₀ (t) = LSB _k (n) , поэтому t нечетно тогда и только тогда, когда установлен LSB _k (n) .

Определение, установлен ли MSB _k (n) , немного сложнее; это то, что n & t > t >> 1достигается. Чтобы проиллюстрировать, как это работает, давайте рассмотрим целое число n = 1αβγδεζη ₂ длиной 8 бит и проанализируем вызов функции F (n, 3) , т. Е. K = 3 .

Мы пытаемся определить, установлено ли значение MSB ₃ (n) = γ , изучая истинное значение сравнения (n & t> t >> 1) = (1αβγδεζη ₂ & 1αβγδ ₂ > 1αβγ ₂ ) . Давайте рассмотрим задействованные целые числа.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

Мы утверждаем, что γ = 1 тогда и только тогда, когда n & t> t >> 1 .

• Если γ = 1 , то n & t имеет битовую длину 5, а t >> 1 имеет битовую длину 4 , поэтому n & t> t >> 1 .

  Это доказывает, что γ = 1 влечет n & t> t >> 1 .

• Если n & t> t >> 1 , есть два варианта: либо γ = 1, либо γ = 0 . В первом случае доказывать нечего.

  Во втором случае имеем, что αβγδ ₂ ≥ n & t> t >> 1 = 1αβγ ₂ .

  Поскольку αβγδ ₂ > 1αβγ ₂ , мы должны иметь MSB ₀ (αβγδ ₂ ) ≥ MSB ₀ (1αβγ ₂ ) , что означает, что α = 1 .

  Таким образом, 1βγδ ₂ > 11βγ ₂ , поэтому мы должны иметь MSB ₁ (1βγδ ₂ ) ≥ MSB ₁ (11βγ ₂ ) , что означает, что β = 1 .

  В свою очередь это означает, что 11γδ ₂ > 111γ ₂ . Вспоминая, что γ = 0 во втором случае, мы получаем неравенство 110δ ₂ > 1110 ₂ , которое неверно, поскольку MSB ₂ (110δ ₂ ) = 0 <1 = MSB ₂ (1110 ₂ ) .

  Таким образом, возможен только первый случай, и n & t> t >> 1 влечет γ = 1 .

Подводя итог, если установлены и LSB _k (n), и MSB _k (n) , t будет нечетным, а n & t> t >> 1 будет истинным , поэтому t & (n & t> t >> 1) будет выход 1 . Однако, если LSB _k (n) или MSB _k (n) не установлены (или если и то и другое), t будет четным или n & t> t >> 1 будет False , поэтому t & (n & t> t> > 1) даст 0 .

Вызов F с одним аргументом инициализирует k = 0 . В то время как условие, которое мы обсуждали ранее, выполняется, выполняется код after and, который (среди прочего) рекурсивно вызывает F с увеличенным k .

Как только LSB _k (n) или MSB _k (n) не установлены, условие не выполняется, и F (n, k) возвращает 0 . Каждый из предыдущих вызовов функции k добавляет (n & (n + 1)> 0) + 1 к F (n, k) = 0 , поэтому F (n) возвращает ((n & (n + 1)> 0) + 1) к .

Теперь, если все биты n равны (то есть, если n равно 0 или все его биты установлены), n + 1 не будет иметь каких-либо общих битов с n , поэтому n & (n + 1) = 0 и F (n) возвращает k . Однако, если n имеет как установленные, так и не установленные биты, n & (n + 1)> 0 и F (n) возвращает 2k .

MATL , 13 12 байт

Btv`6L&)}x@q

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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

B        % Input number (implicit). Horizontal vector of binary digits
tv       % Duplicate and concatenate vertically
`        % Do...while
  6L&)   %   Flatten the array if needed (in column-major order), and split it
         %   into two subarrays: one with the inner entries, and another
         %   with the two outer entries. The latter will be used for deciding
         %   if the loop continues or is exited
}        % Finally (execute before exiting the loop)
  x      %   Delete last subarray of inner entries
  @q     %   Push last iteration index minus 1
         % End (implicit). The next iterarion is executed if the array at the
         % top of the stack is non-empty and only contains nonzero values. 
         % Otherwise the loop is exited, executing the "finally" block first
         % Display (implicit)

Python, 82 байта

Я чувствую, что все еще можно играть в гольф, но я потратил некоторое время, пробуя разные методы, и это был самый короткий путь.

def f(n):b=bin(n)[2:];x=min(b.find('0'),b[::-1].find('0'));print(x<0)*len(b)or x*2

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

Хотя это работает аналогично программе Python для OP, я создал ее до того, как вопрос был опубликован, после просмотра вопроса в Песочнице, в которой не было такой программы.

Python 2, 66 байт

s=bin(input())[2:].split('0')
print len(min(s[-1],s[0]))<<1%len(s)

Разбивает двоичное представление входных данных на порции 1. Подсчитывает количество единиц в меньшем из первого и последнего чанка, затем удваивает его, если только в одном чанке этот счет не удвоится.

PowerShell , 109 106 байт

$a=[convert]::ToString($args[0],2)-split0;(((($b=$a[0].length),$a[-1].length|sort)[0]*2),$b)[$a.count-eq1]

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

Принимает вход $args[0], использует вызов .NET для convertнего toStringс базой 2(то есть, сделать его бинарное), то -splitS , что строка на 0с, магазины, в $a. Важно отметить: вызов .NET не возвращает начальные нули, поэтому первая цифра всегда a 1.

Таким образом, существует две возможности - двоичная строка - все единицы, или был хотя бы один ноль. Мы различаем людей с псевдо-троичным индексом $a.count-eq1. Если в двоичном файле есть хотя бы один ноль, то в левом случае мы берем минимальную длину первой [0]строки 1s и последней [-1]строки (найденных |sortи затем [0]). Чем короче из них, тем больше пар мы можем удалить, поэтому мы умножаем это на 2. Обратите внимание, что если исходная двоичная строка оканчивается на a 0, как для ввода 8, то [-1].lengthтакже будет 0(так как это пустая строка), что при умножении на 2равно 0.

В противном случае, с двоичной строкой, все мы берем just $b(которая ранее была задана равной длине первой [0]строки, в данном случае, всей двоичной строке).

В любом случае этот результат остается в конвейере, а вывод неявным.

JavaScript (ES6), 57 байт

f=
n=>n.toString(2).replace(/^(1*)(.*(\1))?$/,'$1$3').length

<input oninput=o.value=1/this.value?f(+this.value):''><input id=o readonly>

Принимает двоичный файл и пытается сопоставить все 1sили, в случае неудачи, равное количество ведущих и конечных 1s.

Сетчатка , 48 байт

.+
$*
+`(1+)\1
$1o
o1
1
m(+`^1(.*)1$
xx¶$1
x|^1$

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

Объяснение:

.+              # Convert to unary
$*
+`(1+)\1        # Convert to binary (but with `o` instead of `0` -- it's shorter)
$1o
o1
1
m(+`^1(.*)1$    # Replace pairs of surrounding ones with `xx`
xx¶$1
x|^1$,          # Count x's, including the possibility of a single remaining `1`

C #, 133 байта

Функция, которая возвращает твердость. Берет целое число из аргумента.

int h(int b){var n=Convert.ToString(b,2);for(b=0;;){if(n[0]+n[n.Length-1]==98)n=n.Substring(1,n.Length-2);else break;b+=2;}return b;}

Ну а сегодня я узнал '1' + '1' = 98в C #.

C 89 88 85 байт

Сохранено два байта из-за @FlipTack, указывающего на бесполезное объявление.

Вызов f()с номером для проверки, выход возвращается из функции.

t,h;f(l){for(t=l;t&&~t&1<<30;t*=2);for(h=0;t&1<<30&&l&1;t*=2,l/=2)++h;return h<<!!l;}

Попробуйте это на Ideone .

JavaScript (ES6), 59 58 байт

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

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

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

console.log(
  [0, 1, 8, 23, 31, 103, 127, 1877, 2015].map(
    n => n + ' -> ' + f(n)
  ).join('\n')
)

Желе , 14 байт

Eo2
BµŒg.ịṂS×Ç

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

C, 137 132 122 119 117 114 98 94 92 87 85 байт

Время начать играть в гольф B-)

i,j;f(n){for(i=1<<30;i&~n;i/=2);for(j=0;n&i;n/=2,i/=4)j+=~n&1?i=0:2;return j-=n<1*j;}

Вот доказательство

main()
{
  printf("%d %d\n", 0, f(0));
  printf("%d %d\n", 1, f(1));
  printf("%d %d\n", 8, f(8));
  printf("%d %d\n", 23, f(23));
  printf("%d %d\n", 31, f(31));
  printf("%d %d\n", 103, f(103));
  printf("%d %d\n", 127, f(127));
  printf("%d %d\n", 1877, f(1877));
  printf("%d %d\n", 2015, f(2015));
  printf("%d %d\n", 3167, f(3167));
} 

и вывод;

0 0
1 1
8 0
23 2
31 5
103 4
127 7
1877 2
2015 10
3167 4 

Java (OpenJDK) , 181 156 150 байт

n->{int i=0;String s=n.toString(n,2);if(s.matches("1*"))i=s.length();else for(;!s.matches("(.*0)|(0.*)");s=s.substring(1,s.length()-1))i+=2;return i;}

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

Mathematica, 63 56 байт

(2-Min[l=#~IntegerDigits~2])Min[Tr/@Split[l][[{1,-1}]]]&

объяснение

l=#~IntegerDigits~2

Сгенерировать представление base-2 для ввода, заключенное в List. Храните это вl

(2-Min[...])

Если элемент min lравен 1, выведите 1. Если нет, выведите 2. Умножьте это на ...

Split[l]

Разделить lна трассы.

... [[{1,-1}]]

Возьмите первый и последний элемент.

Tr/@ ...

Возьмите сумму обоих.

Min[ ... ]

Найдите меньшее между двумя.

(Умножьте первый результат (1 или 2) на этот результат).

Октава, 56 54 байта

 @(n)cummin(d=dec2bin(n)-48)*cummin(flip(d))'*2^!all(d)

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

Объяснение:

d=dec2bin(n)-48

двоичное представление n

cumd= cummin(d);
cumfd = cummin(flip(d));

Возьмите кумулятивный мин d и кумулятивный мин перевернулd

res = cumd * cumfd ';

сделать матричное умножение

out = res*2^!all(d)

умножить на 2, если все цифры 1;

Pyth, 18 байт

?*FJjQ2lJyhSxR0_BJ

Программа, которая принимает ввод целого числа и печатает результат.

Набор тестов (Первая строка для форматирования)

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

?*FJjQ2lJyhSxR0_BJ  Program. Input: Q
?                   If
  F                 reducing
    jQ2             the binary representation of Q as a list
   J                (store in J)
 *                  by multiplication is truthy:
       lJ            Yield len(J)
                    Else:
          hS         Yield the minimum
            xR0      of the first index of zero
               _BJ   in J and its reverse
         y           * 2
                    Implicitly print

APL, 26 байт

+/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢

Тестовые случаи:

      ( +/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢ ) ¨ 0 1 8 23 31 103 127 1877 2015    
0 1 0 2 5 4 7 2 10

Объяснение:

+ / ∘ (∧ \ ≢ ↑ (ε⊢ (, ∧∧) ¨⌽)) 2⊥⍣¯1⊢

                         ⊢ вход
                    2⊥⍣1 преобразовать в двоичное представление
   ()
        (⊢ ¨⌽) для каждого бита и его соответствующего бита на другой стороне
            (∧) взять логический и оба бита,
             составить список обоих битов,
              Take затем возьмите и из списка и и
         ∊ сгладить результирующий массив
      ↑ ↑ взять только первые N бит, где N является
                                длина исходного списка битов
    Take \ взять логический ход и (оставив только
                                стартовые)
+ / ∘ сумма тех

J, 22 байта

(#<.2*(<.&(#.~)|.))@#:

Это основано на аккуратном приеме, извлеченном из этой задачи .

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

объяснение

(#<.2*(<.&(#.~)|.))@#:  Input: integer n
                    #:  Binary digits of n
(                 )@    Operate on those digits D
               |.         Reverse D
       <.                 Take the minimum of
         &(#.~)           the "trailing truths" of D and reverse(D)
    2*                    Multiply by 2
 #                        The length of D
  <.                      Minimum of length and the previous result

PHP, 83 74 байта

3 + 6 байтов, сохраненных Йоргом

<?=(~$s=decbin($argn))[$a=strspn($s,1)]?min($a,strspn(strrev($s),1))*2:$a;

принимает данные от STDIN; беги с -nR.

сломать

<?=                     # print ...
(~
    $s=decbin($argn)        # $s = binary representation of input
)[
    $a=strspn($s,1)         # $a = number of leading `1`s
]                           # if $s has more than $a digits,
?   min($a,                     # 2. minimum of $a and
        strspn(strrev($s),1)    # 1. number of trailing `1`s
    )*2                         # 3. *2
:   $a                      # else $a (==strlen)

JavaScript (ES6), 83 байта

f=x=>(y=x.toString(2),y.match(/^1*$/)?y:([s,e]=y.match(/^1*|1*$/g),s<e?s:e)).length

Ungolfed:

function f(n) {
    var binStr = n.toString(2);
    if(binStr.match(/^1*$/)) {
        // If binary representation is all 1s, return length of binary
        return binStr.length;
    } else {
        // Grab the starting and ending 1s in the binary representation
        var [start1s, end1s] = binStr.match(/^1*|1*$/g);
        var startHardness = start1s.length;
        var endHardness = end1s.length;
        return Math.min(startHardness, endHardness);
    }
}

Mathematica, 62 байта

(h=0;#~IntegerDigits~2//.{{1,m___,1}:>(h+=2;{m}),{1}:>h++};h)&

Чистая функция где #представляет первый аргумент.

(h=0;...;h)&устанавливает h=0, делает кучу вещей ..., затем возвращает h(твердость). Давайте посмотрим на кучу вещей:

#~IntegerDigits~2                                     Binary representation of the input
                 //.                                  Apply the following list of rules repeatedly until there is no change
                    {                                 Start of the list of rules
                     {1,m___,1}                       If you see a list starting and ending with 1 with the sequence m (possibly empty) in between
                               :>(h+=2;{m}),            replace it with just {m} after incrementing h twice.
                                            {1}       If you see the singleton list {1}
                                               :>h++    replace it with h, then increment h.
                                                    } End of the list of rules

Спасибо Грегу Мартину за то, что познакомил меня с этим трюком .

Haskell , 94 92 байта

b 0=[]
b n=mod n 2:b(div n 2)
h n|(c,_:_)<-span(>0)$zipWith(*)n$reverse n=c++c|1<3=n
sum.h.b

Попробуйте онлайн! Использование:

Prelude> sum.h.b $ 3167
4

Объяснение:
b преобразует число в двоичное и возвращает список нулей и единиц с младшим битом первым. В h, этот список инвертируется и поэлементно умножается на исходный список, а затем span(>0)разделяется после начальных 1s:

       b 3167 = [1,1,1,1,1,0,1,0,0,0,1,1] = n
    reverse n = [1,1,0,0,0,1,0,1,1,1,1,1] = m
zipWith(*)n m = [1,1,0,0,0,0,0,0,0,0,1,1] = z
   span(>0) z = ([1,1],[0,0,0,0,0,0,0,0,1,1])

Результирующий кортеж сопоставляется с шаблоном, (c,_:_)где _:_совпадает с любым непустым списком, поэтому c = [1,1]. Поскольку байты удаляются спереди и сзади, c++c = [1,1,1,1]возвращаются и, наконец, суммируются, чтобы получить цифровую жесткость .

Если второй список кортежа пуст, то двоичное представление содержит только единицы, а число единиц - цифровая жесткость. При неудачном сопоставлении с образцом hвозвращается просто n, что снова суммируется.

Perl 61 байт

sub f{$_=sprintf('%b',pop);length(/0/?/^(1+).*\1$/&&$1x2:$_)}

Суть этого выражения /^(1+).*\1$/в $1том, что ответом в 2 раза больше длины . Остальная часть кода является служебной и связана с особым случаем всего 1.

PHP, 65 байт

<?=strlen(preg_filter('#^(1*)(.*(\1))?$#',"$1$3",decbin($argn)));

Онлайн версия

CJam, 14 байтов

ri2b_0#\W%0#e<

Объяснение:

ri e# Read integer:      | 3167
2b e# Convert to binary: | [1 1 0 0 0 1 0 1 1 1 1 1]
_  e# Duplicate:         | [1 1 0 0 0 1 0 1 1 1 1 1] [1 1 0 0 0 1 0 1 1 1 1 1]
0# e# Index of first 0:  | [1 1 0 0 0 1 0 1 1 1 1 1] 2
\  e# Swap:              | 2 [1 1 0 0 0 1 0 1 1 1 1 1]
W% e# Reverse:           | 2 [1 1 1 1 1 0 1 0 0 0 1 1]
0# e# Index of first 0:  | 2 5
e< e# Minimum:           | 2