Digital Hardness of Integers

Question

To find the digital hardness of an integer, take its binary representation, and count the number of times both a leading and trailing 1 can be removed until it either start or ends with a 0. The total number of bits removed is its digital hardness.

That's quite a wordy explanation - so let's break it down with a worked example.

For this example, we'll use the number 3167. In binary, this is:

110001011111

(Note that, during the conversion to binary, you should make sure to strip leading zeroes)

It doesn't start or end with 0, so we remove 1 pair of bits:

1  1000101111  1

And another:

11  00010111  11

But now there is a 0 at the beginning, so we can't remove anymore 1 pairs. In total, 4 bits we removed, and so 4 is the digital hardness of 3167.

However, for numbers that can be written as 2ⁿ-1 for positive n (i.e. contain only 1 in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length.

---

The Challenge

You task is to write a program or function which, given a non-negative integer n >= 0, determines its digital hardness.

You can submit a full program which performs I/O, or a function which returns the result. Your submission should work for values of n within your language's standard integer range.

---

Test Cases

Please notify me if any of these are incorrect, or if you'd like to suggest any edge cases to add.

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

Here's the ungolfed Python solution which I used to generate these test cases (not guaranteed to be bug-less):

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

Answer 1

Python, 76 69 68 63 62 60 57 bytes

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

Try it online!

How it works

This is a recursive solution that takes an input n and keeps incrementing k – starting at 0– while both LSB_k(n) (bit at index k from the right) and MSB_k(n) (bit at index k from the left) are set. Once finished, it returns k if all of n's bit are set and 2k if not.

Let's start by rewriting the lambda f as a named function F, with an auxiliary variable 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)

In each invocation of F, we first bit-shift n a total of k units to the right and store the result in t. This way, LSB₀(t) = LSB_k(n), so t is odd if and only if LSB_k(n) is set.

Determining whether MSB_k(n) is set is slightly trickier; this is what n & t > t >> 1 achieves. To illustrate how it works, let's consider an integer n = 1αβγδεζη₂ of bit-length 8 and analyze the function call F(n, 3), i.e., k = 3.

We're trying to determine whether MSB₃(n) = γ is set by examining the truth value of the comparison (n & t > t >> 1) = (1αβγδεζη₂ & 1αβγδ₂ > 1αβγ₂). Let's examine the involved integers.

MSB-index  012k4567

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

t >> 1         1αβγ

We claim that γ = 1 if and only if n & t > t >> 1.

• If γ = 1, then n & t has bit-length 5 while t >> 1 has bit-length 4, so n & t > t >> 1.

  This proves that γ = 1 implies n & t > t >> 1.

• If n & t > t >> 1, there are two options: either γ = 1 or γ = 0. In the first case, there's nothing left to prove.

  In the second case, we have that αβγδ₂ ≥ n & t > t >> 1 = 1αβγ₂.

  Since αβγδ₂ > 1αβγ₂, we must have MSB₀(αβγδ₂) ≥ MSB₀(1αβγ₂), meaning that α = 1.

  This way, 1βγδ₂ > 11βγ₂, so we must have MSB₁(1βγδ₂) ≥ MSB₁(11βγ₂), meaning that β = 1.

  In turn, this implies that 11γδ₂ > 111γ₂. Remembering that γ = 0 in the second case, we get the inequality 110δ₂ > 1110₂, which is false since MSB₂(110δ₂) = 0 < 1 = MSB₂(1110₂).

  Thus, only the first case is possible and n & t > t >> 1 implies γ = 1.

Summing up, if both LSB_k(n) and MSB_k(n) are set, t will be odd and n & t > t >> 1 will be True, so t & (n & t > t >> 1) will yield 1. However, if LSB_k(n) or MSB_k(n) is unset (or if both are), t will be even or n & t > t >> 1 will be False, so t & (n & t > t >> 1) will yield 0.

Calling F with a single argument initializes k = 0. While the condition we've discussed earlier holds, the code after and is executed, which (among other things) recursively calls F with incremented k.

Once LSB_k(n) or MSB_k(n) is unset, the condition fails and F(n, k) returns 0. Each of the preceding k function calls adds (n & (n + 1) > 0) + 1 to F(n, k) = 0, so F(n) returns ((n & (n + 1) > 0) + 1)k.

Now, if all bits of n are equal (i.e., if n is either 0 or all of its bits are set), n + 1 will not have any bits in common with n, so n & (n + 1) = 0 and F(n) returns k. However, if n has both set and unset bits, n & (n + 1) > 0 and F(n) returns 2k.

Answer 2

Jelly, 11 10 bytes

BµQL××Ṛa\S

Try it online!

How it works

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.

Answer 3

MATL, 13 12 bytes

Btv`6L&)}x@q

Try it online! Or verify all test cases.

Explanation

The code repeats each binary digit, and counts how many times it is possible to remove two outer ones.

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)

Answer 4

Python, 82 bytes

I feel like it can still be golfed, but I spent a while trying different methods and this was the shortest.

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

Try it online

Though this works similarly to the OP's Python program, I created this before the question was posted, after viewing the question in the Sandbox, which did not contain such a program.

Answer 5

Python 2, 66 bytes

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

Splits the binary representation of the input into chunks of 1. Counts the number of 1's in the smaller of the first and last chunk, then doubles it, unless there's a single chunk that this would double-count.

Answer 6

PowerShell, 109 106 bytes

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

Try it online!

Takes input $args[0], uses the .NET call to convert it toString with base 2 (i.e., make it binary), then -splits that string on 0s, stores that into $a. Important to note: the .NET call does not return leading zeros, so the first digit is always a 1.

There are thus two possibilities -- the binary string is all ones, or there was at least one zero. We differentiate between those with a pseudo-ternary indexed by $a.count-eq1. If the binary has at least one zero, the left case, we take the minimum of the length of the first [0] string of 1s and the last [-1] string (found by |sort and then [0]). The shorter of those is the most pairs we could remove, so we multiply that by 2. Note that if the original binary string ends in a 0, like for input 8, then the [-1].length will also be 0 (since it's an empty string), which when multiplied by 2 is still 0.

Otherwise, with the binary string all ones, we take just $b (which was previously set to be the length of the first [0] string, in this case, the entirety of the binary string).

In either situation, that result is left on the pipeline and output is implicit.

Answer 7

JavaScript (ES6), 57 bytes

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>

Takes the binary and tries to match all 1s or failing that an equal number of leading and trailing 1s.

Answer 8

Retina, 48 bytes

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

Try it online

Explanation:

.+              # 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`

Answer 9

C#, 133 bytes

Function that returns hardness. Takes integer from argument.

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;}

Well, today I found out '1' + '1' = 98 in C#.

Answer 10

C, 89 88 85 bytes

Saved two bytes due to @FlipTack pointing out a useless declaration.

Call f() with the number to test, the output is returned from the function.

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;}

Try it on ideone.

Answer 11

JavaScript (ES6), 59 58 bytes

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

Test cases

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')
)

Answer 12

Jelly, 14 bytes

Eo2
BµŒg.ịṂS×Ç

Try it online!

Answer 13

C, 137 132 122 119 117 114 98 94 92 87 85 Bytes

Time to start golfing 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;}

Here's the proof

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));
} 

and the output;

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

Answer 14

Java (OpenJDK), 181 156 150 bytes

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;}

Try it online!

Answer 15

Mathematica, 63 56 bytes

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

Explanation

l=#~IntegerDigits~2

Generate the base-2 representation of the input, wrapped with a List. Store that in l

(2-Min[...])

If the min element of l is 1, output 1. If not, output 2. Multiply this by...

Split[l]

Split l into runs.

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

Take the first and the last element.

Tr/@ ...

Take the total of both.

Min[ ... ]

Find the smaller between the two.

(Multiply the first result (1 or 2) with this result).

Answer 16

Octave, 56 54 bytes

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

Try it Online!

Explanation:

d=dec2bin(n)-48

binary representation of n

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

Take cumulative min of d and cumulative min of flipped d

res = cumd * cumfd ';

do matrix multiplication

out = res*2^!all(d)

multiply with 2 if all of digits is 1;

Answer 17

Pyth, 18 bytes

?*FJjQ2lJyhSxR0_BJ

A program that takes input of an integer and prints the result.

Test suite (First line for formatting)

How it works

?*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

Answer 18

APL, 26 bytes

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

Test cases:

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

Explanation:

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

                         ⊢   input
                    2⊥⍣¯1    convert to binary representation
   (               )
        (  ⊢    ¨⌽)          for each bit and its matching bit on the other side
            (  ∧)               take the logical and of both bits,
             ,                  make a list of both bits,
              ∧                 then take the and of the list and the and
         ∊                   flatten the resulting array
      ≢↑                     take only the first N bits, where N is the
                                length of the original list of bits
    ∧\                       take a running logical and (leaving only the
                                starting ones)
+/∘                          sum those

Answer 19

J, 22 bytes

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

This is based on the neat trick learned from this challenge.

Try it online!

Explanation

(#<.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

Answer 20

PHP, 83 74 bytes

3+6 bytes saved by Jörg

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

takes input from STDIN; run with -nR.

breakdown

<?=                     # 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)

Answer 21

JavaScript (ES6), 83 Bytes

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);
    }
}

Answer 22

Mathematica, 62 bytes

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

Pure function where # represents the first argument.

(h=0;...;h)& sets h=0, does a bunch of stuff ..., then returns h (the hardness). Let's look at the bunch of stuff:

#~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

Thanks to Greg Martin for introducing me to this trick.

Answer 23

Haskell, 94 92 bytes

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

Try it online! Usage:

Prelude> sum.h.b $ 3167
4

Explanation:
b converts a number to binary and returns a list of zero and ones with the least significant bit first. In h, this list is reversed and element-wise multiplied with the original list, then span(>0) splits after the initial 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])

The resulting tuple is pattern matched with (c,_:_) where _:_ matches any non-empty list, so c = [1,1]. Because the bytes are removed at front and back, c++c = [1,1,1,1] is returned and finally summed up to yield the digital hardness.

If the second list of the tuple is empty, then the binary representation contains ones only, and the number of ones is the digital hardness. With the pattern matching failed h returns just n, which is again summed up.

Answer 24

Perl, 61 bytes

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

The heart of this is the regex /^(1+).*\1$/ where 2 times the length of $1 is the answer. Rest of the code is overhead and dealing with the all 1's special case.

Answer 25

PHP, 65 Bytes

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

Online Version

Answer 26

CJam, 14 bytes

ri2b_0#\W%0#e<

Explanation:

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