Introduction
In Encode's Cairo Bootcamp, there is an interesting bit manipulation challenge. It took me some time to figure it out. In this article, I will discuss the challenge and the solution.
The challenge
ex7.cairo
%lang starknet
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.math import unsigned_div_rem
// Using binary operations return:
// - 1 when pattern of bits is 01010101 from LSB up to MSB 1, but accounts for trailing zeros
// - 0 otherwise
// 000000101010101 PASS
// 010101010101011 FAIL
func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
return (0,);
}
test_ex7.cairo
%lang starknet
from starkware.cairo.common.uint256 import Uint256
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin, HashBuiltin
from exercises.programs.ex7 import pattern
@external
func test_patternt{syscall_ptr: felt*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*}() {
alloc_locals;
// test nice numbers
//###############################################################################################
let (nice_pattern) = pattern(n=170, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 1;
let (nice_pattern) = pattern(n=10, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 1;
let (nice_pattern) = pattern(n=43690, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 1;
let (nice_pattern) = pattern(n=1398101, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 1;
// test not-nice numbers
//###############################################################################################
let (nice_pattern) = pattern(n=17, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 0;
let (nice_pattern) = pattern(n=11, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 0;
let (nice_pattern) = pattern(n=43390, idx=0, exp=0, broken_chain=0);
assert nice_pattern = 0;
%{
if ids.nice_pattern == 1:
print(f"has nice pattern")
else:
print(f"doesn't have a nice pattern")
%}
return ();
}
Understanding the problem
If the bit pattern is 01010101, it is valid. Looking at the test cases, we can see that 01010 (decimal 10) is valid too. This means that the problem is about alternative bits between 1 and 0. If the alternative pattern is not broken until the LSB, we return 1, otherwise, return 0. For instance, we will get 1 for 01010 (decimal 10), and 0 for 01011 (decimal 11).
Since the challenge gives us the test cases, we can get some cues about the arguments from them. There are 4 arguments in the pattern function:
n: feltis the decimal number that we want to check its bit pattern. This tells us that we need to convert the decimal number to binary.idx: feltis the index of a bit in the pattern.exp: feltis the value of a bit. We need this because we want to compare adjacent bits to see if the chain is valid.broken_chain: feltThe name says it all. It is like a "boolean" variable that determines whether the pattern is broken.
Solution
func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
if (remainder == exp) {
return 1;
}
return 0;
}
func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
if (n == 0) {
let valid_chain = 1 - broken_chain;
return (valid_chain,);
}
if (broken_chain == 1) {
let valid_chain = 1 - broken_chain;
return (valid_chain,);
}
if (idx == 0) {
let (quotient, remainder) = unsigned_div_rem(n, 2);
let new_idx = idx + 1;
return pattern(quotient, new_idx, remainder, 0);
}
let (quotient, remainder) = unsigned_div_rem(n, 2);
let _broken_chain = check_broken_chain(remainder, exp);
let new_idx = idx + 1;
return pattern(quotient, new_idx, remainder, _broken_chain);
}
Explain the solution
The solution can be broken down into 3 simple steps :
- Convert the decimal
nto binary - Check if the pattern is valid
- Handle edge case and base case
Convert the decimal n to binary
One way to convert decimal to binary is to use modulo. Cairo does not have a built-in modulo operator, but we can use unsigned_div_rem from Starkware math library.
from starkware.cairo.common.math import unsigned_div_rem
let (quotient, remainder) = unsigned_div_rem(n, 2);
Check if the pattern is valid
Simply put, It comes down to whether the current bit remainder is different than the previous bit exp. If they are the same, the pattern is broken.
When I first tried to handle the _broken_chain value, I did this:
let (quotient, remainder) = unsigned_div_rem(n, 2);
tempvar _broken_chain = 0;
if (remainder == exp) {
_broken_chain = 1;
}
let new_idx = idx + 1;
return pattern(quotient, new_idx, remainder, _broken_chain);
and got an error
An ASSERT_EQ instruction failed: 0 != 1.
_broken_chain = 1;
^***************^
The reason is that Cairo's memory cell is read-only. Read more about it here.
A workaround is to make a standalone function:
func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
if (remainder == exp) {
return 1;
}
return 0;
}
...
let (quotient, remainder) = unsigned_div_rem(n, 2);
let _broken_chain = check_broken_chain(remainder, exp);
let new_idx = idx + 1;
return pattern(quotient, new_idx, remainder, _broken_chain);
Since the challenge has a bitwise_xor import in the first place, we can also use it to get the _broken_chain use like so:
let (remainder_xor_prev_remainder) = bitwise_xor(remainder, exp);
let _broken_chain = 1 - remainder_xor_prev_remainder;
During the recursion, if broken_chain is 1, we just return the result.
if (broken_chain == 1) {
let valid_chain = 1 - broken_chain;
return (valid_chain,);
}
Handle the edge case and base case
The first bit does not have a previous bit to compare with, so we can just calculate its remainder and move to the next bit.
if (idx == 0) {
let (quotient, remainder) = unsigned_div_rem(n, 2);
let new_idx = idx + 1;
return pattern(quotient, new_idx, remainder, 0);
}
Because we keep dividing n by 2, it will become 0 eventually. When it does, we return the result.
if (n == 0) {
let valid_chain = 1 - broken_chain;
return (valid_chain,);
}
Wrapping Up
Alright, that is all I am covering for today. If you have any questions, please feel free to reach out to me. I hope this is helpful to somebody learning Cairo.
You can find the code in this article on Github