Daily Challenge #257 - Halving Sum

Given a positive integer n, calculate the following sum:
n + n/2 + n/4 + n/8 + ...

All elements of the sum are the results of integer division. Continue dividing the number until you reach a decimal (no decimals allowed in final answer).

Example
25 => 25 + 12 + 6 + 3 + 1 = 47

Tests
halvingSum(25)
halvingSum(127)

---

This challenge comes from Belia on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Mike Talbot ⭐]

const half = n => n > 0 ? n + half(n>>1) : n

[Mihail Malo]

const half = n => n && half(n>>1) + n

:v

[Amin]

Haskell

halvingSum :: Int -> Int
halvingSum 0 = 0
halvingSum x = (+) x $ halvingSum $ div x 2

[Pierre Bouillon]

Verbose C# solutions 😄

[Swarup Das]

/**
 * 
 * @param {Number} number 
 */
function halvingSum(number) {
    let total = 0;
    while (number > 0) {
        total += number;
        number = Math.floor(number / 2);
    }
    return total;
}

[Blake Johnson]

C

int halving_sum(int n) {
    if (n / 2 <= 1) return n + 1;
    return n + halving_sum(n / 2);
}

[David Leger]

Looping

const halvingSum = (n: number): number => {
  let sum = 0;

  while (n !== 0) {
    sum += n;
    n = Math.floor(n / 2);
  }

  return sum;
}

Recursion

const halvingSum = (n: number): number => {
  if (n === 0) {
    return n;
  }

  return n + halvingSum(Math.floor(n / 2))
}

Tail Recursion

const halvingSum = (n: number, sum: number = 0): number => {
  if (n === 0) {
    return sum;
  }

  return halvingSum(Math.floor(n / 2), sum + n);
}

[Anna]

COBOL

Run it at jdoodle.com/a/280D

IDENTIFICATION DIVISION.
PROGRAM-ID. HALVING-SUM.
DATA DIVISION.
    WORKING-STORAGE SECTION.
        01 WS-NUMBER PIC 9(4).
        01 WS-SUM PIC 9(5) VALUE 0.
PROCEDURE DIVISION.
    DISPLAY 'Enter number from 1 to 9999:'
    ACCEPT WS-NUMBER FROM CONSOLE       
    PERFORM UNTIL WS-NUMBER < 1
        ADD WS-NUMBER TO WS-SUM
        DIVIDE WS-NUMBER BY 2 GIVING WS-NUMBER
    END-PERFORM     
    DISPLAY WS-SUM.     
STOP RUN.

[Vidit Sarkar]

Here is a Python solution,

halvingSum = lambda n : n and (n + halvingSum(n >> 1))

print(halvingSum(25)) # output -> 47
print(halvingSum(127)) # output -> 247

[Sam Ferree]

Befunge-93

&>:02pv
      >2/:0`!#v_:02g+02p
              >02g.@

Edit:
Here is a version with comments

&>:02pv Read a value t from the user, store it at (0,2)
         divide t by 2, if t > 0 store (0,2)+t at (0,2) repeat
      >2/:0`!#v_:02g+02p
                if t <= 0 print (0,2) as integer, end program
              >02g.@

[Austin Nieset]

Learning Typescript

function halvingSum(num: number): number {
    if (num <= 1) {
        return 0;
    } else {
        return num + Math.floor(halvingSum(num/2));
    }
}