Data Structures Homework :D

[Zeruel]

Hello guys! 

 

I recently finished my data structures HW and though I post it here for people to get an idea of what coding can be like and get feedback :3

 

Im not allowed to use the % operator or MATH libraries. 

/** * NAME * SCHOOL * CLASS * PROFESSOR  * Warm-up Programming Project # 0 * * Function 1: Reads a positive integer number and counts the number of bits in its * binary representation (as an unsigned integer), not including the leading zeros. * * Function 2: Reads positive integer numbers n and m and quickly computes the * value of the remainder 2^n (2 to power n) mod m. */public class Project_0{        public static String binaryString( int x )        {            String binaryString = "";            while( x != 0 )            {                if((x/2)*2 == (x - 1))                {                    binaryString = binaryString + "1";                }                else                {                    binaryString = binaryString + "0";                }                x = x/2;            }            char[] inArray =  binaryString.toCharArray();            char[] outArray = new char[binaryString.length() ];            int a = 0;            for( int i = inArray.length - 1; i >= 0; i-- )            {                outArray[a++] = inArray[i];            }            binaryString = new String( outArray );            return binaryString;        }        public static int computeRemainder(int n, int m )        {            int remainder = 2;            boolean check = false;            String binaryString = binaryString(n);            char[] binaryStringArray = binaryString.toCharArray();            int[][] storage = new int[binaryString.length()][2];            for( int i = 0; i < binaryString.length(); i++ )            {                if( binaryStringArray[i] == '1' )                {                    storage[i][0] = 1;                }                else                {                    storage[i][0] = 0;                }                check = false;                if( remainder < m )                {                    storage[i][1] = remainder;                    remainder = (remainder * remainder);                }                else                {                    while( check == false )                    {                        remainder = remainder - m;                        if( m > remainder )                        {                          storage[i][1] = remainder;                          remainder = ( remainder * remainder );                          check = true;                        }                    }                }            }            int a = binaryString.length()-1;            remainder = 1;            for( int i = 0; i < binaryString.length(); i++ )            {                if( storage[a--][0] == 1 )                {                    remainder = (remainder * storage[i][1]);                }            }            check = false;            if( remainder < m )            {            }            else            {                while( check == false )                {                    remainder = remainder - m;                    if( m > remainder )                    {                        check = true;                    }                }            }            return remainder;        }        public static void main(String[] args)        {            int x = 1234567;            String binaryRep = "";            System.out.printf( "FUCNTION ONE -->\n" );            binaryRep = binaryString(x);            System.out.printf( "Integer: %d\nBinary Representation: %s\nNumber of Bits: %d\n",x , binaryRep, binaryRep.length() );            System.out.println();            System.out.println("FUNCTION TWO -->");            int n = 63;            int m = 1023;            if( m == 0 )            {                System.out.printf( "n = %d\nm = %d\n2^(%d) mod %d = %s\n\n", n, m, n, m, "INDETRMINATE!" );            }            else            {                System.out.printf( "n = %d\nm = %d\n2^(%d) mod %d = %d\n\n", n, m, n, m, computeRemainder(n, m) );            }            System.out.print("End.");        }}

[79wjd]

when would (x/2)*2 == (x - 1)) ever be true? 

 

And, now its time to go through it and try to make it as short as possible. 

[Ciccioo]

Hello guys! 

I recently finished my data structures HW and though I post it here for people to get an idea of what coding can be like and get feedback :3

 

Im not allowed to use the % operator or MATH libraries.

well, the program could be much faster and shorter if you think of a way to mathematically solve those two problems

this is a neat exercise to apply a little algebra (function 2) and binary math, maybe with java bitwise operators (function 1)

 

when would (x/2)*2 == (x - 1)) ever be true?

for odd x

[MrSuperb]

int a = 0;for( int i = inArray.length - 1; i >= 0; i-- ){    outArray[a++] = inArray[i];}

really?

[WanderingFool]

What Ciccioo said about bitwise for function one.

In case you aren't familiar with bitwise  (n >> 1) == (n / 2) and (n << 1) == n * 2 and you can lookup the bitwise operator & (if you want to be the most efficient)

 

A few other notes, Stringbuilder in java is a handy class (it is suppose to be more efficient than constantly adding to strings) so I would look it up.

In terms of building the string and then reversing the string, ask yourself is it necessary?

Why do

//Why dobinaryString = binaryString + "1";....[binaryString reverse]//when you can dobinaryString = "1" + binaryString;...[No need to reverse]

For function 2, I am sorry it is too early for me to read through it and figure out what you are doing...but I would like to say this.

While I am aware the problem is (2^n) mod m...there would have been a trick if it were reversed m mod (2^n)...but alas no such luck.

[Zeruel]

Thanks for the help you guys! You all pointed out very good ways to optimize my code  

 

My HW is due tomorrow so I will work on it some more