Skip to main content
Code Golf

Return to Answer

Correct a comment in the dissection
Source Link
Peter Taylor
Peter Taylor
  • 43.4k
  • 4
  • 72
  • 179

CJam (22 bytes)

This is one byte longer than the current best CJam answer, but the approach can probably be adapted to some other languages quite profitably.

3,ri_2b_,,:).*\+fbW%:-

Online demo

Analysis

Suppose that the question were

calculate the sum of the sub-strings of the binary number

without the bit

whose length is shorter than the original number

Then it's not too hard to show that the most significant bit occurs with total weight 1*(2^B-1) where B is the number of bits; the second-most significant bit occurs with total weight 2*(2^(B-1)-1); down to the Bth-most significant bit, which occurs with total weight B*(2^1-1).

Taking into account now the subtraction of the original number, x, we end up with the sum

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Dissection

3,        e# Put [2[0 1 0]2] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

The conversion to base 2 gives the first part of the main sum plus x; to base 1 gives the second part plus x; and to base 0 gives just x, so subtracting the base-1 from the base-2 the xs cancel, and subtracting the base-0 gives the desired result.

CJam (22 bytes)

This is one byte longer than the current best CJam answer, but the approach can probably be adapted to some other languages quite profitably.

3,ri_2b_,,:).*\+fbW%:-

Online demo

Analysis

Suppose that the question were

calculate the sum of the sub-strings of the binary number

without the bit

whose length is shorter than the original number

Then it's not too hard to show that the most significant bit occurs with total weight 1*(2^B-1) where B is the number of bits; the second-most significant bit occurs with total weight 2*(2^(B-1)-1); down to the Bth-most significant bit, which occurs with total weight B*(2^1-1).

Taking into account now the subtraction of the original number, x, we end up with the sum

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Dissection

3,        e# Put [2 1 0] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

The conversion to base 2 gives the first part of the main sum plus x; to base 1 gives the second part plus x; and to base 0 gives just x, so subtracting the base-1 from the base-2 the xs cancel, and subtracting the base-0 gives the desired result.

CJam (22 bytes)

This is one byte longer than the current best CJam answer, but the approach can probably be adapted to some other languages quite profitably.

3,ri_2b_,,:).*\+fbW%:-

Online demo

Analysis

Suppose that the question were

calculate the sum of the sub-strings of the binary number

without the bit

whose length is shorter than the original number

Then it's not too hard to show that the most significant bit occurs with total weight 1*(2^B-1) where B is the number of bits; the second-most significant bit occurs with total weight 2*(2^(B-1)-1); down to the Bth-most significant bit, which occurs with total weight B*(2^1-1).

Taking into account now the subtraction of the original number, x, we end up with the sum

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Dissection

3,        e# Put [0 1 2] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

The conversion to base 2 gives the first part of the main sum plus x; to base 1 gives the second part plus x; and to base 0 gives just x, so subtracting the base-1 from the base-2 the xs cancel, and subtracting the base-0 gives the desired result.

Source Link
Peter Taylor
Peter Taylor
  • 43.4k
  • 4
  • 72
  • 179

CJam (22 bytes)

This is one byte longer than the current best CJam answer, but the approach can probably be adapted to some other languages quite profitably.

3,ri_2b_,,:).*\+fbW%:-

Online demo

Analysis

Suppose that the question were

calculate the sum of the sub-strings of the binary number

without the bit

whose length is shorter than the original number

Then it's not too hard to show that the most significant bit occurs with total weight 1*(2^B-1) where B is the number of bits; the second-most significant bit occurs with total weight 2*(2^(B-1)-1); down to the Bth-most significant bit, which occurs with total weight B*(2^1-1).

Taking into account now the subtraction of the original number, x, we end up with the sum

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Dissection

3,        e# Put [2 1 0] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

The conversion to base 2 gives the first part of the main sum plus x; to base 1 gives the second part plus x; and to base 0 gives just x, so subtracting the base-1 from the base-2 the xs cancel, and subtracting the base-0 gives the desired result.