Skip to content

Instantly share code, notes, and snippets.

@BonfaceKilz
Last active March 18, 2021 13:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save BonfaceKilz/1ccb79a9bc943661837cd791660e99ce to your computer and use it in GitHub Desktop.
Save BonfaceKilz/1ccb79a9bc943661837cd791660e99ce to your computer and use it in GitHub Desktop.
00 Bit Reversal

Prelude

Hi folks! Much appreciation for last week's submissions!

I've been looking at Spritely Goblins(https://docs.racket-lang.org/goblins/intro.html), which is an object system following the actor model. I want to try to use it to hack something up(in GUILE) that can monitor different machines in a cluster(assuming an agent is present in each node) What's interesting, is some of the historical context from which it borrows some of it's implementations from. You can read some of that here: http://erights.org/elib/distrib/captp/index.html. Ports of Goblins to other PL would be really cool!

Last Week's Challenge

Issue 2: https://is.gd/EKppEK

Mailing List Discussion: https://is.gd/WVnUzj

If you get the bandwidth, hack at the problems at the submission links above-- It's a nice way to get comments on your code \m/\m/.

This Week's Challenge

Source: Anonymous

Reverse the bits given a binary number

Constraints: Do not do any string conversion(and string reversal)!

Examples:
Input: n = 0b1011
Output: 0b1101

Post your answers here as comments.

@kodesoul
Copy link

kodesoul commented Mar 4, 2021

This feels like cheating but here is the actual code I'd use in production.

fn reverse_bits(num : u32) -> u32 {
     num.reverse_bits()
}

I'll post an imperative algorithm in a few.

@kodesoul
Copy link

kodesoul commented Mar 4, 2021

Solution in Rust

fn reverse_bits(num: i32) -> i32 {
    // Create mutable variables
    let mut rev = 0;
    let mut num = num;

    // check if number has been shifted to zero
    while num > 0 {
        // Increase place values adding zero to the end.
        rev <<= 1;

        // check if last digit is 1
        // if so add it to rev.
        if num & 1 == 1 {
            rev ^= 1;
        }

        // shift num to the left
        num >>= 1;
    }
    rev
}

@ianmuchina
Copy link

python solution

def bin_reverse(num):
    rev = 0
    
    while(num):
        # Make space in rev
        rev <<= 1

        # Copy rightmost digit in num to rev
        rev += num & 1

        # Delete rightmost digit in num
        num >>= 1

    return rev

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment