Binary Calculator

The Usual Tricks Instructions First Version - Stack based Second Version - Grammar added Third Version - Files separated Gains from Experience

toggle TOC (ctrl + ⇔)

Source on github
Many programming contests require performance critical solutions (like many real life applications), which is often provided by clever manipulation of bit arrays. I made this calculator to practice bit manipulation and familiarize myself with more C++ along the way.

See the github repository for the latest description of the project; this page is out of date.
























Bincalc was cross compiled from C++ to JS using Emscripten, and run with jq-console

Fullscreen bincalc

The Usual Tricks

basics

x ^ 0 = x

x & 0 = 0

x | 0 = x

x ^ ~0 = ~x

x & ~0 = x

x | ~0 = ~0

x ^ x = 0

x & x = x

x | x = x
get, set, go

get ith bit

x & (1 << i)

set ith bit

x | (1 << i)

clear ith bit

x & ~(1 << i)

filter out bits above i

x & ((1 << i) - 1)

filter out bits below i

x & ~((1 << i) - 1)

extract n bits starting above i

x & (~(~0 << n) << i)
least significant bit

clear least significant bit

x & (x - 1)

check if x is a power of 2

x & (x - 1) == 0

Instructions

  1. Clone code from github or using cmd `git clone git://github.com/LemonPi/bincalc.git`
  2. Try **bc-windows** on windows, and on **bc-linux** on linux, else build it by following the rest of the steps
  3. Build with `make` in the directory if you have g++(gcc) with c++11 support
  4. Else either change (CC) in the makefile to your compiler of choice, or build with another tool
  5. Run with `./bc` or `bc` on windows in terminal
  6. Tips:
    • exit with `Ctrl + c`
    • adjust how many binary digits is shown by changing `bit_num` in consts.h
    • 0xnum is **hex**, 0num is **oct**, and bnum is **binary**
    • change underlying type (default is double) by changing `rep_type` in consts.h

Example usage (bc is directly called because I copied it to /usr/local/bin)

First Version - Stack based

Restricting users to RPN input and not having variables were the biggest usability flaws. The largest technical weakness is its lack of modularity in keeping everything (reading from input, processing input, error handling) in one giant function. This makes it hard add features since everything depends on everything else in the function and order matters.

Second Version - Grammar added

The largest usability flaw is restricting the user to positive integers (which is sufficient for bit manipulation practice). Many of the first version's flaws were a result of design rather than technical deficiency. Adding features to it would be hacky and difficult. I overhauled the design by introducing grammar, which naturally implements order of operations. Rules of grammar:

The grammar is intuitively and efficiently handled by a recursive descent parser (inspired by Bjorne Stroustrup's desk calculator in The C++ Language 4th edition, chapter 10.2). Each level of the parser calls the next, with each level applying its rules and returning its value. For example, in expr(), it expects at least a base term rep_type left = term(need_get); and adds or subtracts all additional terms it can 

while (true) {
    switch (ts.current().kind) {
        case Kind::plus: left += term(true); break;
        case Kind::minus: left -= term(true); break;
        default: return left;
    }
}
Separation of concerns and keeping it modular makes adding features and understanding the code much easier. Here, expr() doesn't have to worry about the implementation at the lowest level, it just needs term() to follow the rules and return the value of a term. This sort of intuitive logic propagates all the way down to the lowest level, prim(), where actual parsing of values happen.

prim() ultimately needs to tokens to parse, which comes from the lexer. The lexer's job is to process state and value information from a input stream into tokens.

The other components include a table/dictionary to hold name-value information for variables, a simple error handling function, and a driver to start the parser.

Third Version - Files separated

The missing features of the second version were easily added due to the modular design. The feature complete second version had no usability flaws, but it could be improved technically by enforcing modularity further from separation of functions to separation of files. The interface could also be removed from the implementation by separating header and source files.

As the diagram shows, each part relies only on other parts' interface, never their implementation. Version 2 roughly had this, but version 3 strictly enforces it. The conceptual benefits include more abstraction (without overhead) and modularity, making it easy to understand and add features. The technical benefits include stronger error safety and faster compile time, since files that haven't changed doesn't need to be recompiled. These benefits are much more important as project sizes scale up.

Gains from Experience