Diluted Integer Sums

Question

A positive integer can be diluted by inserting a 0 between two bits in its binary expansion. This means that an n-bit number has n-1 dilutions, which are not necessarily all distinct.

For example, for 12 (or 1100 in binary), the dilutions are

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

In this challenge, we're going to be taking the sum of all the dilutions, exclusive of the original number. For 12, taking the sum of 24, 24, 20 results in 68, so 68 should be the output for 12.

Challenge

Given a positive integer n > 1 as input, output/return the diluted sum as explained above.

Examples

in    out
---   ---
2       4
3       5
7      24
12     68
333  5128
512  9216

Rules

• The input and output can be assumed to fit in your language's native integer type.
• The input and output can be given in any convenient format.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

Python 2, 43 39 bytes

f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

Try it online!

---

How?

Each call of the recursive function calculates a single dilution. The position of the inserted 0 is log2(i). The function recurses until i gets bigger than n and the insertion would be on the left of the number. If i>n, n/i evaluates to 0, which is a falsy value in Python.

n*2 shifts the entire number one binary digit left, n%i or n % 2**(position of insertion) calculates the value of the part that should not be shifted left. This value gets subtracted from the shifted number.

Example (n=7)

call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0

Answer 2

Jelly, 11 bytes

BJṖ2*ɓdḅḤ}S

Try it online!

How it works

BJṖ2*ɓdḅḤ}S  Main link. Argument: n (integer)

B            Binary; convert n to base 2. This yields a digit array A.
 J           Indices; yield [1, ..., len(A)].
  Ṗ          Pop; remove the last element, yielding [1, 2, ..., len(A)-1].
   2*        Elevate 2 to these powers, yielding [2, 4, ..., 2**(len(A)-1)].
             Let's call the result B.
     ɓ       Begin a new, dyadic chain, with left argument n and right argument B.
      d      Divmod; yield [n/b, n%b], for each b in B.
        Ḥ}   Unhalve right; yield 2b for each b in B, i.e., [4, 8, ..., 2**len(A)].
       ḅ     Unbase; convert each [n/b, n%b] from base 2b to integer, yielding
             (2b)(n/b) + (n%b).
          S  Take the sum.

Answer 3

MATL, 13 bytes

tZl:W&\5ME*+s

Try it at MATL Online! Or verify all test cases.

Explanation

Consider input 12 as an example.

t     % Implicit input. Duplicate
      % STACK: 12, 12
Zl    % Binary logarithm
      % STACK: 12, 3.584962500721156
:     % Range (rounds down)
      % STACK: 12, [1 2 3]
W     % Power with base 2, element-wise
      % STACK: 12, [2 4 8]
&\    % 2-output modulus, element-wise: pushes remainders and quotients
      % STACK: [0 0 4], [6 3 1]
5M    % Push array of powers of 2, again
      % STACK: [0 0 4], [6 3 1], [2 4 8]
E     % Multiply by 2
      % STACK: [0 0 4], [6 3 1], [4 8 16]
*     % Multiply, element-wise
      % STACK: [0 0 4], [24 24 16]
+     % Add, element-wise
      % STACK: [24 24 20]
s     % Sum of array. Implicit display
      % STACK: 68

Answer 4

Japt, 12 11 bytes

¢¬£¢iYTÃÅxÍ

Try it

---

Explanation

                 :Implicit input of integer U
¢                :Convert to base-2 string
 ¬               :Split to an array of individual characters/digits
  £    Ã         :Map over the elements, with Y being the current 0-based index
   ¢             :  Convert U to a base-2 string
    iYT          :  Insert a 0 in that string at index Y
        Å        :Slice off the first element of the array
          Í      :Convert each element to a base-10 integer
         x       :Reduce by addition

Answer 5

C,  58  56 bytes

Thanks to @Dennis for saving two bytes!

s,k;f(n){for(s=0,k=2;k<=n;k*=2)s+=n/k*k*2+n%k;return s;}

Try it online!

C (gcc), 50 bytes

s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k+=k);k=s;}

Returning by k=s; is undefined behaviour, but works with gcc when optimizations are disabled. Also, n%k+n/k*(k+=k) has unspecified behaviour, but seems to work fine with gcc.

Try it online!

Answer 6

J, 20 15 14 bytes

+/@}:@:+[\&.#:

Try it online.

15 bytes

1#.-,+:-#.\.@#:

Try it online!

     +:             Input×2
       -            Subtract
        #.\.@#:     The list of binary suffixes of input (in decimal)
   -,               Append negative input
1#.                 Add them up

Answer 7

Jelly, 9 8 bytes

BḊḄÐƤạḤS

Try it online!

B                        to binary          42 -> 1 0 1 0 1 0
 Ḋ                       drop first                 0 1 0 1 0
  ḄÐƤ                    each suffix to decimal   10 10 2 2 0
      Ḥ                  double the input                  84
     ạ                   absolute difference   74 74 82 82 84
       S                 add them up                      396

Vice versa, B¹ƤṖ+BḄS: get prefixes, drop last, add them to input, and sum.

Answer 8

JavaScript (ES6), 41 40 bytes

Saved 1 byte thanks to Mr.Xcoder

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

Test cases

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

console.log(f(2  )) //    4
console.log(f(3  )) //    5
console.log(f(7  )) //   24
console.log(f(12 )) //   68
console.log(f(333)) // 5128
console.log(f(512)) // 9216

Answer 9

Retina, 53 50 47 bytes

.+
*
+`(_+)\1
$1O
O_
_
L$`\B
$`O$'
+%`\B
¶$`¶
_

Try it online! Link includes test cases. Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

.+
*
+`(_+)\1
$1O
O_
_

Convert from decimal to binary, but using O to represent 0, as it's not a digit, and _ to represent 1, as it's the default repetition character in Retina 1.

L$`\B
$`O$'

Insert an O between each pair of digits, and collect the results as a list.

+%`\B
¶$`¶

Convert from binary to unary. (This conversion produces extra Os, but we don't care.)

_

Sum and convert to decimal.

Answer 10

Pyth, 13 bytes

smiXd.BQZ2Ssl

Try it here!

Explanation

smiXd.BQZ2Ssl | Full program.

           sl | The base-2 logarithm of the input, floored to an integer.
          S   | Create the integer range [1 ... the floored logarithm].
 m            | And map a function over it.
------------+-+-----------------------------------------------------
  iXd.BQZ2  | The function to be mapped (uses a variable d).
     .BQ    | In the binary representation of the input...
   X    Z   | ... Insert a zero...
    d       | ... At index d.
  i      2  | And convert the result from base 2 to an integer.
------------+-+-----------------------------------------------------
s             | Sum the resulting list.

Answer 11

Jelly, 10 bytes

BµLḤ_J’×µḄ

Try it online!

Not the shortest currently, but it could be if there's a way around Bµ µḄ...

Explanation

BµLḤ_J’×µḄ    Main link. Argument: n (integer)
B             Binary; convert n to an binary of binary digits. Call this A.
 µ            Start a new monadic link with argument A.
  L           Length; yield len(A). We'll call this l.
   Ḥ          Unhalve; yield l * 2.
     J        Length range; yield [1, 2, ..., l].
    _         Subtract; yield [l*2 - 1, l*2 - 2, ..., l].
      ’       Decrement; subtract one from each item.
       ×      Multiply each item by the corresponding item in A. Call this B.
        µ     Start a new monadic link with argument B.
         Ḅ    Unbinary; convert from a binary array to a decimal.

Basically, this works by multiplying each binary digit by a magic number. I can't explain it without visualizing it, so here's the binary number we'll be working with:

1111

As explained by the challenge, he output we want is the sum of these binary numbers:

10111  = 2^4 + 2^2 + 2^1 + 2^0
11011  = 2^4 + 2^3 + 2^1 + 2^0
11101  = 2^4 + 2^3 + 2^2 + 2^0

However, we don't actually have to insert zeroes: Jelly's "unbinary" atom will accept numbers other than just 0 and 1. When we allow ourselves to use 2, this pattern gets simpler:

2111   = 2*2^3 + 1*2^2 + 1*2^1 + 1*2^0
2211   = 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0
2221   = 2*2^3 + 2*2^2 + 2*2^1 + 1*2^0

When we sum up the digits in each column, we get

6543   = 6*2^3 + 5*2^2 + 4*2^1 + 3*2^0 = 48 + 20 + 8 + 3 = 79.

The trick this answer uses is to generate this pattern, and multiply each digit by the corresponding digit in the original to cancel out the necessary columns. 12, for example, would be represented as

 1100
×6543
=6500  = 6*2^3 + 5*2^2 + 0*2^1 + 0*2^0 = 48 + 20 + 0 + 0 = 68.

Answer 12

Husk, 13 12 bytes

-1 byte thanks to @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

Try it online!

Explanation

ṁḋ§z·+Θḣ(tṫ)ḋ  -- example input: 6
            ḋ  -- convert to binary: [1,1,0]
  §            -- fork argument
        (tṫ)   -- | tail of tails: [[1,0],[0]]
       ḣ       -- | heads: [[1],[1,1],[1,1,0]]
   z           -- and zipWith the following (example with [1,0] [1])
    · Θ        -- | prepend 0 to second argument: [0,1]
     +         -- | concatenate: [1,0,0,1]
               -- : [[1,0,1,0],[1,1,0,0]]
ṁ              -- map the following (example with [1,0,1,0]) and sum
 ḋ             -- | convert from binary: 10
               -- : 22

Answer 13

Java 8, 55 bytes

n->{int r=0,i=2;for(;i<=n;r+=n%i+n/i*(i*=2));return r;}

Port of Steadybox' C answer, and golfed 3 bytes in the process.

Try it online.

Answer 14

R, 141 48 bytes

function(n,l=2^(1:log2(n)))sum(n%%l+(n%/%l*2*l))

Try it online!

Either I'm doing something really wrong or R is just terrible at bit manipulation. Porting Luis Mendo's approach is easy, correct, and golfy.

But if you really just want to muck around with bit operations, MickyT suggested the following 105 byter:

function(i)sum(sapply(1:max(which(b<-intToBits(i)>0)),function(x)packBits(head(append(b,F,x),-1),"i")))-i

Try it online!

Answer 15

Python 3, 92 80 78 bytes

def b(x):x=f'{x:b}';return sum(int(x[:i]+'0'+x[i:],2)for i in range(1,len(x)))

Try It Online

Thanks to Mr.XCoder and ovs for -12 bytes and -2 bytes respectively.

Answer 16

05AB1E, 14 bytes

.²LoDŠ‰ø`r·*+O

Try it online!

Answer 17

Batch, 92 77 bytes

@set/an=2,t=0
:l
@if %1 geq %n% set/at+=%1*2-(%1%%n),n*=2&goto l
@echo %t%

Edit: Switched to the same formula everyone else is using.

Answer 18

Pip, 21 18 bytes

2*a-a%2**_MS1,#TBa

Try it online!

Explanation

Call our input number a. For each binary index i at which we want to insert a zero, we can calculate the bits left of the insertion point as a // 2**i (where // is integer division and ** is exponentiation), the bits right of the insertion point as a % 2**i, and therefore the diluted integer as 2 * (a // 2**i) * 2**i + (a % 2**i). But (a // 2**i) * 2**i is equal to a - (a % 2**i), and so we can rearrange to a shorter formula: 2 * (a - a % 2**i) + a % 2**i = 2 * a - a % 2**i.

2*a-a%2**_MS1,#TBa
                       a is 1st command-line argument (implicit)
               TBa     Convert a to binary
              #        Length of the binary expansion
            1,         Range from 1 up to (but not including) that number
          MS           Map this function to the range and sum the results:
2*a-a%2**_              The above formula, where _ is the argument of the function
                       The final result is autoprinted

Answer 19

Jelly, 14 bytes

BLḊṬœṗ¥€Bj€0ḄS

Try it online!

Answer 20

Perl 5, 36 + 1 (-p) = 37 bytes

$\+=$_*2-($_&$.-1)while($.*=2)<=$_}{

Try it online!

Answer 21

Attache, 57 bytes

Sum##UnBin=>{Join[Join=>_,"0"]}=>SplitAt#1&`:@{#_-1}##Bin

Try it online!

I thought I'd approach the problem from a non-bit manipulation approach, as such an approach is impractical in Attache. I have to investigate some of the parts of this approach for alternatives.

Explanation

Here is an expanded version:

Define[$joinByZero, {Join[Join=>_,"0"]}]

Define[$insertionPoints,
    SplitAt#1&`:@{#_-1}
]

Define[$f,
Sum##UnBin=>joinByZero=>insertionPoints##Bin
]

This simply takes the binary representation of the number, splits it at certain points, inserts zeroes there, converts back to decimal, and sums them together.

Answer 22

J, 33 bytes

1#.[:}:#.@(<\;@(,0;])"0<@}.\.)@#:

Most probably there is much room for further golfing.

How?

@#: convert to binary and

<@}.\. - find all suffices, drop the first digit from each and box

<\ - find all prefixes and box them

(,0;])"0 - to each prefix append 0 then append the corresponding beheaded suffix

;@ raze (unbox)

1#.[:}:#.@ - convert to decimal, curtail and sum

Try it online!