Thread: Modulus to Bitwise

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    27

    Modulus to Bitwise

    Essentially I'm doing an assignment of a loop with 9973 integers in an array (closest prime to 10,000 so dual loops are needed), adding them up, and doing this 200,000 times. It's an assignment about unrolling and efficiency in building loops.

    Just to say, we're specifically not allowed to have the compiler optimize.

    All that said, we have different targets for different grades, and while I've gone from 16.5 seconds (starting code) to about 7.7-7.9 seconds, I'm still in need of shaving several seconds. I'm hoping I can get down to 2-3 (as that approaches his records.)
    (Just for fun, those are averages, and my lowest code so far on it's best run is ~7.1)

    My problem is in the limitations of what code we can change, and my stubbornness to make my code robust, so that ANY size of an array may be used, I'm stuck with a modulus; essentially a division running 200,000 times. If anyone knows clock cycles, you know a division is about 30 times worse than additions or bit-wise operations.


    So with all of that out of the way
    Question
    I've heard you can use the logical AND to turn moduli of the form (2^n) into bitwise functions of the form ((2^n)-1). I.E. You could AND the ARRAY_SIZE with '7' (if doing 8 unrolls) and get the remainder.

    I tried simply doing: efficientRemainder = ARRAY_SIZE && 7 (and similar), but this is quite wrong. Or the source is incorrect.


    If I could have any advice on either getting this bitwise operation to work, or another way to avoid this modulus with robust code, I'd appreciate it. I might try a Do While loop to get rid of it, but it's easy to start accessing unused or incorrect memory when you're unrolling a Prime. Modulus or similar was my first thought, and while it works, I fear that it is the majority of my overhead.
    Last edited by blurrymadness; 12-01-2009 at 12:32 PM.

  2. #2
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413
    ARRAY_SIZE && 7
    && is logical AND, you want &

    You can do modulos with numbers in the form of 2^n by doing a bitwise AND with 2^n-1, i.e.

    x%8 is the same as x&7
    x%32 is the same as x&31

    i.e. 31%8=7 and also 31&7=7

    This is because of the fact that 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise Questions
    By someprogr in forum C Programming
    Replies: 8
    Last Post: 12-14-2008, 06:45 PM
  2. bitwise operations with double
    By henry_kay in forum C Programming
    Replies: 2
    Last Post: 10-03-2007, 04:57 AM
  3. Palindromes and Bitwise operators
    By Dr Tornillo in forum C Programming
    Replies: 8
    Last Post: 08-02-2007, 02:31 PM
  4. Characters into bitwise ints
    By Code Zer0 in forum C++ Programming
    Replies: 9
    Last Post: 04-24-2003, 08:34 AM
  5. using modulus & weighting factors
    By task in forum C Programming
    Replies: 4
    Last Post: 09-11-2002, 05:52 PM