Function 1: Reads a positive integer number and counts the number of bits in its
ID: 3561300 • Letter: F
Question
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.
Hint. Use this property: (a^n) mod m = (a * a * a *...* a) mod m =
= (...(((((a mod m) * a) mod m) * a) mod m) *...* a) mod m.
For instance,
(2^4) mod 7 = (2 * 2 * 2 * 2) mod 7 =
= ((((((2 mod 7) * 2) mod 7) * 2) mod 7) * 2) mod 7 =
= (((((2 * 2) mod 7) * 2) mod 7) * 2) mod 7 =
= ((((4 mod 7) * 2) mod 7) * 2) mod 7 =
= (((4 * 2) mod 7) * 2) mod 7 =
= (1 * 2) mod 7 =
= 2 mod 7 = 2.
In order to avoid overflow, you may use this property:
(a * 2) mod m = a * 2 if a < m/2,
(a * 2) mod m = (a - m) + a if a >= m/2.
This way you compute
(((4 * 2) mod 7) * 2) mod 7 = (((4 - 7) + 4) * 2) mod 7 = (1 * 2) mod 7 without use of numbers greater than 7.
Explanation / Answer
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; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.