Digital Hardness of Integers 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 2n-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 &gt;= 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     -&gt; 0
1     -&gt; 1
8     -&gt; 0
23    -&gt; 2
31    -&gt; 5
103   -&gt; 4
127   -&gt; 7
1877  -&gt; 2
2015  -&gt; 10


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

def hardness(num) -&gt; 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
Python, 76 69 68 63 62 60 57 bytes



f=lambda n,k=0:n&gt;&gt;k&amp;(n&amp;n&gt;&gt;k&gt;n&gt;&gt;k+1)and(n&amp;n+1&gt;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 LSBk(n) (bit at index k from the right) and MSBk(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 &gt;&gt; k
    return t &amp; (n &amp; t &gt; t &gt;&gt; 1) and (n &amp; (n + 1) &gt; 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, LSB0(t) = LSBk(n), so t is odd if and only if LSBk(n) is set.

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

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

MSB-index  012k4567

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

t &gt;&gt; 1         1αβγ


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


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

This proves that γ = 1 implies n &amp; t > t >> 1.
If n &amp; 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 αβγδ2 ≥ n &amp; t > t >> 1 = 1αβγ2.

Since αβγδ2 > 1αβγ2, we must have MSB0(αβγδ2) ≥ MSB0(1αβγ2), meaning that α = 1.

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

In turn, this implies that 11γδ2 > 111γ2. Remembering that γ = 0 in the second case, we get the inequality 110δ2 > 11102, which is false since MSB2(110δ2) = 0 &lt; 1 = MSB2(11102).

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


Summing up, if both LSBk(n) and MSBk(n) are set, t will be odd and n &amp; t > t >> 1 will be True, so t &amp; (n &amp; t > t >> 1) will yield 1. However, if LSBk(n) or MSBk(n) is unset (or if both are), t will be even or n &amp; t > t >> 1 will be False, so t &amp; (n &amp; 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 LSBk(n) or MSBk(n) is unset, the condition fails and F(n, k) returns 0. Each of the preceding k function calls adds (n &amp; (n + 1) > 0) + 1 to F(n, k) = 0, so F(n) returns ((n &amp; (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 &amp; (n + 1) = 0 and F(n) returns k. However, if n has both set and unset bits, n &amp; (n + 1) > 0 and F(n) returns 2k.