# Using Hamming Codes to implement number of “1” bits
contributed by: <`weishiuan`>

## Motivation

Modify the code from [LeetCode: Number of "1" bits](https://leetcode.com/problems/number-of-1-bits/ "游標顯示")

As we know, hamming codes are used for error detection and correction in digital data transmission and storage systems. They add redundant bits to data to identify and fix single-bit errors, enhancing data reliability in applications like computer memory and communication systems.

For example:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

## Implememt

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight/ "游標顯示")).

#### C Code

#include <stdio.h>
#include <stdint.h>

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main() {
    volatile char* c_1 = (volatile char*)0x40002000;
    volatile int* c_2 = (volatile int*)0x40000008;

    int n = 2147483647;
    int count = hammingWeight(n);

    char* str = "The number of \"1\" bits of ";
    while (*str) {
        *c_1 = *str;
        str++;
    }

    *c_2 = n;
    str = " is ";
    while (*str) {
        *c_1 = *str;
        str++;
    }

    *c_2 = count;
    return 0;
}

## Disassembly an ELF file

One commonly used tool for disassembling ELF files is 'objdump', which is part of the GNU Binutils suite. We can use it from the command line like this:

`objdump -d your_executable_or_object_file`

Compile into 3 level with command: `riscv32-unknown-elf-g++ -march=rv32i -mabi=ilp32 -o output.elf input.cpp`

* -O0: This is a basic and straightforward implementation

0800010c <cntbit>:
 800010c:	00053663          	beqz	a1,800012c <cntbit+0x20>
 8000110:	00050513          	mv	a0,a0
 8000114:	fff3ff06          	srl	a4,a0,a5
 8000118:	ffe3ff06          	and	a4,a0,a4
 800011c:	00062683          	beqz	a4,8000130 <cntbit+0x24>
 8000120:	00153513          	addi	a0,a0,1
 8000124:	fff3ff06          	srl	a4,a0,a5
 8000128:	ffe3ff06          	and	a4,a0,a4
 800012c:	ff5ff06f          	j	800012c <cntbit+0x20>
 8000130:	00158513          	li	a1,1
 8000134:	0010106f          	jr	810
 8000138:	00008067          	ret

* -O1: Basic Implementation with Compiler Optimization

0800020c <cntbit>:
 800020c:	ffff0f06          	slli	a5,a0,0x1f
 8000210:	00553513          	srli	a0,a0,0x1
 8000214:	fe3ff06f          	jr	    8000210 <cntbit+0x4>
 8000218:	00008067          	ret

* -O3: Optimized Implementation with Compiler Optimization

0800030c <cntbit>:
 800030c:	ffe30713          	andi	a4,a0,0xfe0
 8000310:	fff3ff06          	srl	a5,a0,a5
 8000314:	00062683          	beqz	a4,8000318 <cntbit+0xc>
 8000318:	ffe3ff06          	and	a4,a0,a4
 800031c:	00153613          	addi	a2,a0,1
 8000320:	00053713          	li	a3,0
 8000324:	00051513          	mv	a0,a0
 8000328:	0043b0a3          	mv	a1,a5
 800032c:	ff13b06f          	jal	8000310 <cntbit+0x4>
 8000330:	00008067          	ret

## Analysis

* -O0
Execute Time: Run the slowest because it contains redundant or unoptimized code
Stack Usage: Have a larger memory footprint
Instruction Counts: Highest

* -O1
Execute Time: Faster than "-O0" but less than "-O3"
Stack Usage: Reduce some memory usage to basic operation
Instruction Counts: Medium

* -O3
Execute Time: Fastest execution
Stack Usage: Minimal
Instruction Counts: Optimized to minimize instruction count

## Experiment

:::success
* -O0
>The number of "1" bits of 26112097 is 9
>Execution time: 143549 ns
>Instruction count: 354
:::

:::success
* -O1
>The number of "1" bits of 26112097 is 9
>Execution time: 135446 ns
>Instruction count: 148
:::

:::success
* -O3
>The number of "1" bits of 26112097 is 9
>Execution time: 542865 ns
>Instruction count: 63
:::

:::warning
You shall use RDCYCLE/RDCYCLEH instruction for the statistics of your program’s execution.
:notes: jserv
:::