BonfaceKilz/00 Binary Weight.md

#[test]
fn test() {
    assert_eq!(3, number_of_1_bits(00000000000001011));
    assert_eq!(1, number_of_1_bits(0000100000));
    assert_eq!(10, number_of_1_bits(11111111110));
}

fn number_of_1_bits(x: u64) -> usize {
    let bin = x.to_string();

    bin.chars()
        .filter(|ch| *ch == '1')
        .count()
}

The rust solution to leetcode (https://is.gd/lR9u7I)

fn hammingWeight(n: u32) -> i32 {
    n.count_ones() as i32 
}

Solution in C :

int hammingWeight(unsigned int number) {
  int oneCount = 0;

  //Loop till number is zero
  while (number != 0) {

    // If right most digit is "1"
    if (number & 1) {      

      // Increment count   
      oneCount = oneCount + 1;
    }

    // Remove right most digit with right shift >>
    number = number >> 1;
  }
  return oneCount;
}

https://stackoverflow.com/q/33005271

@princebett counting the 1's in the string works; though the idea of this imho is to fiddle with bits. Here's one clever way of doing it:

def hamming_weight(bin_num: int) -> int:
    """Get the number of on bits given a BIN_NUM which is a binary
number"""
    count = 0
    while True:
        if bin_num == 0:
            break
        bin_num &= bin_num - 1
        count += 1

    return count

print(hamming_weight(0b11101))  # => 4
print(hamming_weight(0b11101111))  # => 7
print(hamming_weight(0b0))  # => 0

I've done it Python since IMHO it's easier to read. I'll try posting one in scheme later today :)

@BonfaceKilz Thanks for the clarification. Went into a little deep dive on Binary operations and I now understand why your code works. Below is a rust translation.

fn hammingWeight(n : u32) -> i32 {
    let mut count = 0;
    let mut n = n;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    count
}

I'll look into how to rewrite that in a more declarative way (without using recursion). I really don't like mutable anything.

@princebett, it's important to note that Rust doesn't really support TCO atm of this writing; thereby writing recursive fns is ill-advised. For big inputs, you have the possibility of getting some stack overflow. With that said, if you have to use a tail-recursive call, you could pull in extra deps that "trampoline"[0] your tail-recursive functions :)

[0] Trampolining is a technique that converts tail recursive fns into their iterative equivalents, thereby only using one stack frame

Tramp.rs actually does some heap allocation making it slower than just looping.

So, I felt a little weird, like I was cheating with the code above, since I did not actually compute the binary values myself. As such, just to assuage my critical voices, here's the new code, with my own computation of the binary values:

#lang racket
(require racket/contract)

(module+ test
  (require rackunit)
  (check-equal? (hamming-weight #b00000000000001011) 3)
  (check-equal? (hamming-weight #b0000100000) 1)
  (check-equal? (hamming-weight #b11111111110) 10)
  (check-equal? (hamming-weight 5) 2))

(define/contract (nonnegative-integer->binary-list n)
  (-> exact-nonnegative-integer?
      (listof (lambda (x) (or (zero? x) (= x 1)))))
  (define (->binary quot binlist)
    (cond
      [(zero? quot) binlist]
      [(->binary (quotient quot 2) (cons (modulo quot 2) binlist))]))
  (cond
    [(or (zero? n) (= n 1)) (cons n '())]
    [else (->binary (quotient n 2) (cons (modulo n 2) '()))]))

(define/contract (hamming-weight v)
  (-> exact-nonnegative-integer? exact-nonnegative-integer?)
  (length
   (filter (lambda [n] (= n 1))
	   (nonnegative-integer->binary-list v))))