---

The Ultimate Guide to Bit Counting in Cairo: Mastering the Eliud's Eggs Challenge

To count the number of set bits (1s) in the binary representation of a number in Cairo, you can iteratively check the last bit using the modulo operator (% 2) and then right-shift the bits by dividing the number by 2, repeating this process until the number becomes zero.

---

The Mystery of the Digital Chicken Coop

Imagine this: your friend Eliud inherits a futuristic farm where the chicken coop isn't just wood and wire, but a marvel of technology. A digital display shows a single, cryptic number. This number, a legacy from her inventive grandmother, isn't the egg count itself. Instead, it's an encoded map where each '1' in the number's binary form represents a nest with an egg ready for collection.

You're staring at a number like 13. To a human, it's just thirteen. But to the coop's system, it's 1101 in binary. This means there are eggs in the 1st, 3rd, and 4th positions (reading from right to left). The total number of eggs is 3. Eliud is stumped, and the chickens are waiting. She turns to you, her programmer friend, with a simple request: "Can you write a program to decode this and tell me the actual number of eggs?"

This challenge, straight from the exclusive kodikra.com learning path, isn't just about helping a friend. It's a gateway to understanding one of the most fundamental operations in computer science: bit counting. In this guide, we'll dissect this problem from zero to hero, exploring the logic, implementing a solution in Cairo, and even uncovering more efficient, professional-grade techniques.

---

What Exactly is Bit Counting? (The "Hamming Weight" Explained)

At its core, the problem asks us to find the Hamming weight of a number. This is a formal term for counting the number of set bits—the '1's—in its binary representation. It's also known as the "population count" or simply "popcount."

Every number stored in a computer is ultimately a sequence of 0s and 1s. For example, the unsigned 64-bit integer (u64) for the number 75 is:

0000000000000000000000000000000000000000000000000000000001001011

The Hamming weight of 75 is 4, because there are four '1's in its binary form. Our task is to write a function that takes any number (like 75) and returns its Hamming weight (4).

Why is this a Core Computer Science Concept?

You might wonder why we can't just use a built-in function. The goal of this kodikra module is to build your understanding from the ground up. Bit manipulation is the bedrock of low-level programming and performance optimization. Understanding how to count bits manually is crucial for:

• Cryptography: Many cryptographic algorithms rely heavily on bitwise operations for their security and efficiency.
• Error Detection & Correction: Hamming codes, which use bit parity to detect and correct errors in data transmission, are built on these principles.
• Data Compression: Algorithms often analyze bit patterns to find redundancies and compress data effectively.
• Blockchain & ZK-Circuits: In environments like Cairo and StarkNet, every computation step has a cost. Efficient, low-level algorithms directly translate to cheaper transaction fees. Understanding bit manipulation is non-negotiable for writing optimized smart contracts.

---

How to Solve Eliud's Eggs: The Foundational Algorithm

To solve this problem without using a built-in library function, we need a reliable algorithm to inspect every bit of the input number. The most intuitive method involves a simple loop that repeatedly checks the last bit and then "removes" it.

This approach is often called the "Check and Shift" or "Modulo and Divide" method. The logic is straightforward:

1. Start with a count of 0.
2. Take the input number. As long as it's not zero, repeat the next steps.
3. Check if the number is odd. In binary, if the last bit is 1, the number is odd. We can check this with the modulo operator: number % 2 == 1.
4. If it is odd, we've found a set bit, so we increment our count.
5. "Remove" the last bit. We can do this with integer division by 2 (number / 2). This effectively performs a right bit shift, moving all bits one position to the right and discarding the last one.
6. Once the number becomes 0, all bits have been checked. The loop terminates.
7. Return the final count.

Let's trace this with the number 13 (binary 1101):

• Start: current = 13, count = 0
• Iteration 1: 13 % 2 == 1 is true. Increment count to 1. Update current to 13 / 2 = 6.
• Iteration 2: 6 % 2 == 0 is false. Do nothing to count. Update current to 6 / 2 = 3.
• Iteration 3: 3 % 2 == 1 is true. Increment count to 2. Update current to 3 / 2 = 1.
• Iteration 4: 1 % 2 == 1 is true. Increment count to 3. Update current to 1 / 2 = 0.
• Iteration 5: current is now 0. The loop breaks.
• End: Return count, which is 3. Correct!

Visualizing the Logic Flow

Here is a modern ASCII diagram that illustrates the flow of the Modulo and Divide algorithm.

    ● Start(number)
    │
    ▼
  ┌──────────────────┐
  │ count = 0        │
  │ current = number │
  └─────────┬────────┘
            │
            ▼
    ◆ current == 0? ──── Yes ───▶ ● Return count
    │
    No
    │
    ▼
┌───────────────────┐
│ Is last bit set?  │
│ (current % 2 == 1)│
└─────────┬─────────┘
          │
    Yes ╱   ╲ No
       │     │
       ▼     │
┌──────────────┐
│ count += 1   │
└───────┬──────┘
        │
        └──────────┐
                   │
                   ▼
         ┌─────────────────┐
         │ Shift bits right│
         │ current /= 2    │
         └─────────┬───────┘
                   │
                   └───────── Loop back to check current ─┐
                                                          │
◄─────────────────────────────────────────────────────────┘

---

Deep Dive: A Line-by-Line Code Walkthrough in Cairo

Now, let's translate our algorithm into functional Cairo code. The solution provided in the kodikra module is a clean and direct implementation of the logic we just discussed. This code is designed for clarity and correctness, making it a perfect starting point.

Here is the complete function from our exclusive Cairo curriculum:

pub fn eggCount(number: u64) -> u64 {
    let mut count = 0;
    let mut current = number;

    loop {
        if current == 0 {
            break;
        }

        if current % 2 == 1 {
            count += 1;
        }

        current /= 2;
    }

    count
}

Let's break this down piece by piece to understand what every line does and why it's there.

pub fn eggCount(number: u64) -> u64 {

• pub fn: This declares a public function, meaning it can be called from other modules or contracts.
• eggCount: This is the name of our function, descriptive of its purpose.
• (number: u64): This defines the function's single parameter. number is the name of the variable, and u64 is its type—an unsigned 64-bit integer. This means it can hold any positive whole number from 0 up to 2⁶⁴-1.
• -> u64: This specifies the return type. Our function will return a value of type u64, which will be the final count of set bits.

let mut count = 0;

• let: The keyword to declare a new variable.
• mut: This keyword makes the variable mutable. By default, variables in Cairo (like in Rust) are immutable. Since we need to update the count inside our loop, we must explicitly mark it as mutable.
• count = 0: We initialize our counter to zero. This variable will store the final result.

let mut current = number;

• This line creates a mutable copy of the input number. It's good practice to work on a copy rather than modifying the original function parameter directly, especially in more complex scenarios. We need this variable to be mutable because we will be dividing it by 2 in each loop iteration, changing its value until it becomes 0.

loop { ... }

• This is Cairo's infinite loop construct. The code inside the curly braces {...} will execute repeatedly forever unless we explicitly tell it to stop using a break statement. This is perfect for our algorithm, as we want to keep processing until a specific condition (current == 0) is met.

if current == 0 { break; }

• This is our exit condition. At the beginning of each iteration, we check if our current number has been reduced to zero. If it has, it means we have checked all the bits, and our work is done. The break; statement immediately exits the loop.

if current % 2 == 1 { count += 1; }

• This is the heart of the logic. The modulo operator % gives the remainder of a division. current % 2 will be 1 if current is odd and 0 if it's even.
• In binary, a number is odd only if its rightmost bit (the least significant bit) is 1. So, this line is a clever way to check the last bit.
• If the condition is true, we've found a set bit, and we increment our counter using count += 1;.

current /= 2;

• This line prepares for the next iteration. Integer division by 2 (/= 2 is shorthand for current = current / 2) has the same effect as a right bit shift operation (>> 1).
• For example, if current is 13 (binary 1101), dividing by 2 gives 6 (binary 110). The last bit has been effectively discarded, and the next bit is now in the last position, ready to be checked in the next loop iteration.

count

• In Cairo, the last expression in a function without a semicolon is implicitly returned. This line simply returns the final value of our count variable after the loop has finished.

---

Can We Optimize This? Exploring Bitwise Operations

The "Modulo and Divide" method is perfectly correct and easy to understand. However, in performance-critical contexts like Cairo, it's worth asking: can we do better? The answer is yes, by using bitwise operations directly.

A famously clever and often more efficient method is Brian Kernighan's Algorithm. This algorithm has a fascinating property: the number of iterations in its loop is equal to the number of set bits. This is a huge improvement over our previous method, which always iterates as many times as there are total bits in the number (or until it's zero).

How Brian Kernighan's Algorithm Works

The magic lies in a single, elegant operation: n & (n - 1).

• & is the bitwise AND operator. It compares two numbers bit by bit and returns a new number where a bit is set to 1 only if it was 1 in both original numbers.
• The expression n - 1 has a neat effect in binary: it flips the rightmost set bit of n to 0, and flips all the bits to the right of it to 1.

Let's see this with n = 76 (binary 01001100):

• n is 01001100
• n - 1 (which is 75) is 01001011
• n & (n - 1) gives:

  01001100  (76)
& 01001011  (75)
----------
  01001000  (72)

Notice what happened? The operation n & (n - 1) turned off the rightmost '1' bit of n. By repeating this operation until the number becomes zero and counting how many times we do it, we find the total number of set bits.

Optimized Cairo Implementation

Here's how you could implement Brian Kernighan's algorithm in Cairo:

pub fn eggCount_optimized(mut number: u64) -> u64 {
    let mut count = 0;

    loop {
        if number == 0 {
            break;
        }

        // This operation clears the least significant set bit
        number = number & (number - 1);
        count += 1;
    }

    count
}

This version directly modifies the `number` parameter (marked as `mut`). In each step, it increments the count and clears one set bit. The loop will run exactly as many times as there are eggs, which is a significant performance gain for "sparse" numbers (numbers with few set bits).

Visualizing the Kernighan Algorithm Flow

This ASCII diagram illustrates the more efficient, jump-based logic of the Kernighan algorithm.

    ● Start(number)
    │
    ▼
  ┌───────────┐
  │ count = 0 │
  └─────┬─────┘
        │
        ▼
    ◆ number == 0? ──── Yes ───▶ ● Return count
    │
    No
    │
    ▼
  ┌──────────────────┐
  │ count += 1       │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Clear rightmost  │
  │ set bit:         │
  │ n = n & (n - 1)  │
  └─────────┬────────┘
            │
            └────────── Loop back to check number ─┐
                                                   │
◄──────────────────────────────────────────────────┘

---

Pros and Cons of Different Bit Counting Approaches

Choosing the right algorithm depends on the context. While micro-optimizations can seem trivial, they add up in gas-sensitive environments like StarkNet. Let's compare the two methods we've discussed.

Attribute	Modulo and Divide	Brian Kernighan's Algorithm
Readability	Excellent. The logic is very intuitive for developers of all levels.	Good, but requires understanding of bitwise operations. The n & (n - 1) trick is not immediately obvious to beginners.
Performance	Consistent. The number of iterations depends on the position of the most significant bit (e.g., ~64 iterations for a large u64).	Variable and often superior. The number of iterations is equal to the number of set bits. It's much faster for numbers with few '1's.
Cairo/StarkNet Context	Safe and reliable. The operations (modulo, division) are standard but can be more computationally expensive than bitwise operations.	Highly preferred. Bitwise operations are typically faster and consume fewer computational resources (gas), making this the go-to for on-chain logic.
Best For	Learning the fundamental principles of binary representation and loops.	Production code, performance-critical applications, and smart contract development where efficiency is key.

---

Putting It All Together: Testing Your Cairo Code

Writing code is only half the battle; ensuring it works correctly is just as important. Cairo has a built-in testing framework that makes this easy. To test our eggCount function, you would create a test module.

First, make sure your function is part of a library. In your `src/lib.cairo` file, you would have your function:

// src/lib.cairo
pub fn eggCount(number: u64) -> u64 {
    // ... implementation from above ...
}

Then, you can add tests, either in the same file or a separate one:

#[cfg(test)]
mod tests {
    use super::eggCount;

    #[test]
    fn test_zero_eggs() {
        assert(eggCount(0) == 0, '0 should have 0 eggs');
    }

    #[test]
    fn test_one_egg() {
        assert(eggCount(16) == 1, '16 has one egg'); // 16 is 10000
    }

    #[test]
    fn test_multiple_eggs() {
        assert(eggCount(75) == 4, '75 has four eggs'); // 75 is 1001011
    }

    #[test]
    fn test_all_eggs_set_for_u8() {
        // 255 is 11111111 in binary
        assert(eggCount(255) == 8, '255 has eight eggs');
    }
}

To run these tests, you would navigate to your project's root directory in the terminal and execute the command provided by the Scarb package manager:

scarb test

The test runner will compile your code and execute each function marked with `#[test]`. If all assertions pass, you'll get a success message, confirming that your egg-counting logic is flawless.

---

Frequently Asked Questions (FAQ)

1. What is Hamming Weight and why is it called that?

Hamming Weight is the number of non-zero symbols in a sequence. In the context of binary numbers, it's the count of '1's. It's named after Richard Hamming, a pioneering mathematician and computer scientist who did foundational work in information theory and error-correcting codes.

2. Why did the kodikra module ask me not to use a built-in function?

The purpose of this specific module in the kodikra learning path is to ensure you understand the fundamental algorithms at play. Relying on a built-in function like .count_ones() (which exists in languages like Rust) would teach you the syntax but not the underlying computer science, which is crucial for becoming a proficient systems or smart contract developer.

3. Is n % 2 == 1 the same as a bitwise operation?

Functionally, yes. n % 2 == 1 checks if the last bit is a 1. A more direct and often faster way to do this is with the bitwise AND operator: (n & 1) == 1. This operation isolates the last bit, and both achieve the same result. The bitwise version is generally preferred in low-level or performance-sensitive code.

4. How would these algorithms work for larger numbers like u128 or u256?

The beauty of these algorithms is that they work perfectly for any unsigned integer size. The logic remains identical. The "Modulo and Divide" method would simply take more iterations for a larger number type (up to 128 or 256 iterations in the worst case), while the performance of Brian Kernighan's algorithm would still only depend on the number of set bits, regardless of the integer's total size.

5. What makes Brian Kernighan's algorithm so special?

Its elegance and efficiency. Instead of ploddingly checking every single bit, it cleverly "jumps" from one set bit to the next (by clearing the rightmost one). This makes its performance proportional to the answer itself, not the size of the input data, which is a powerful algorithmic concept.

6. Why is algorithmic efficiency so critical in Cairo?

Cairo is a language for writing provable programs, primarily for the StarkNet ZK-Rollup. Every computation step in a Cairo program must be "proven," and this process has a cost. More efficient algorithms result in fewer computation steps, which translates directly to lower gas fees for users interacting with your smart contract. An inefficient bit-counting function in a frequently called contract could be prohibitively expensive.

7. Where can I learn more about bit manipulation?

Bit manipulation is a deep and rewarding topic. Continuing through the Cairo curriculum on kodikra.com will expose you to more advanced use cases. Additionally, classic computer science resources like the book "Hacker's Delight" are fantastic for mastering these low-level tricks.

---

Conclusion: From Eggs to Expertise

We started with a simple story about counting eggs and ended with a deep dive into binary representation, algorithmic thinking, and performance optimization in Cairo. The Eliud's Eggs challenge is more than just a puzzle; it's a perfect illustration of how a real-world problem can be solved by applying fundamental computer science principles.

You've learned not just one, but two robust methods for counting set bits: the intuitive "Modulo and Divide" approach and the highly efficient "Brian Kernighan's Algorithm." You now understand the trade-offs between readability and performance and why, in a resource-constrained environment like StarkNet, every operation matters. This knowledge is a stepping stone to writing more complex, optimized, and cost-effective Cairo programs.

Disclaimer: The code and concepts discussed are based on Cairo version 2.6+ and the Scarb package manager. As the Cairo ecosystem evolves, always refer to the official documentation for the latest syntax and best practices.

---

Published by Kodikra — Your trusted Cairo learning resource.