Binary string remainder 3

Question 1

Since you said "string", I'll add the following technique:

Note that if you append 0 at the end of a binary number, you double it's value. If you append 1 at the end, you double it and add 1.

That is, if you have processed all digits up to a certain digit (call this number up to that digit a), and you know that a % 3 = x for some x=1, 2 or 0, then you can tell the following:

a0 % 3 = (2 * a) % 3 = ((2 % 3) * (a % 3)) % 3 = (2 * (a % 3)) % 3
a1 % 3 = (2 * a + 1) % 3 = ((2 % 3) * (a % 3) + (1 % 3)) % 3 = (2 * (a % 3) + 1) % 3

This way, you can easily make the following distinction:

Current mod | Next digit | New mod
------------+------------+---------
   0            0            0
   0            1            1
   1            0            2
   1            1            0
   2            0            1
   2            1            2

That is, you can traverse your string from left to right (assuming msbf notation) and update the new mod according to the table. You start with current mod = 0.

Question 2

it's very fast and innovative.

3 in binary is 11 i.e. 11 in base 10. So we know a number is divisible by 11, if the difference of the sum of digits at odd places and the sum of its digits at even places, is either 0 or divisible by 11.

So add the even placed 1s and add the odd placed 1. Take difference. Please check the below program, we are doing exactly same thing. If you have string same also applies.

public static boolean isDivisible(int n){
    if(n<0){
        n=-n;
    }
    if(n==0)return true;
    if(n==1)return false;
    int even=0, odd=0;
    while(n!=0){
        if((n&1)==1){
            odd++;
        }
        n=n>>1;
        if(n==0)break;
        if((n&1)==1){
            even++;
        }
    }
    return isDivisible(even-odd);
}

For more you can follow this and this.

Question 3

If You notice 2^N mod 3 = 2 if N is odd & 2^N mod 3 = 1 if N is even (it can be proved by induction) moreover binary no is sum of powers of 2 so just check if 1 appear in string at odd or even power and do a running sum of the values. There is theorem in modular arithmatic as

(a+b+c)%m = ((a)%m + (b)%m + (c)%m )%m

eg.

x = 1101 there are 2 even powers of 2 (2^0,2^2) and 1 odd power of 2 (2^3)

hence res = (2*1 + 2 )mod 3 = 4 mod 3 = 1

Java implementation: -

public class Modulus {

    public static int modulo3(String s) {

        int end = s.length()-1;
        int sum = 0;
        for(int i =0;i<s.length();i++) {

           if(s.charAt(end)=='1') {
               if(i%2==0)
                   sum = sum + 1;
               else sum = sum + 2;
           } 

           end--; 
        }
       return(sum%3); 
    }


    public static void main(String[] args) {

        System.out.println(modulo3("1110"));
    }

}

Question 4

A % B is equivalent to A - (floor(A/B) * B). If you can perform subtraction, multiplication, and integer division with your binary numbers, than you can simulate the % operator without actually using it.

Question 5

To tell if a decimal number is divisible by 9 in base 10, just add its digits together and repeat until you have just one digit. If that digit is 0, 3, 6, or 9, then it's divisible by 9.

This works based on the same principle, but for numbers divisible by 3 in base 4:

int mod3 (int x) {
  if (x<0) x = -x;
  while (x & 0x7fff0000) x = ((x & 0x7fff0000)>>16) + (x & 0x0000ffff);
  while (x & 0xff00) x = ((x & 0xff00)>>8) + (x & 0x00ff);
  while (x & 0xf0) x = ((x & 0xf0)>>4) + (x & 0x0f);
  while (x & 0x0c) x = ((x & 0x0c)>>2) + (x & 0x03);
  while (x>=3) x -= 3;
  return x;
}

Question 6

The concept here is if you add 0 or 1 at end of any binary number then number will be doubled plus 0 or 1 based on next bit set or not and reminder will also become [previous_reminder*2 + (0 or 1)]. And to calculate reminder after this step: reminder = reminder%3;

Here is java Code:

public static void main(String[] args) {
    int[] arr = { 1, 1, 0, 1, 1, 0, 0, 1, 1, 1};
    // Assumed first bit is always set therefore reminder will be 1.
    int reminder = 1;

    for (int i = 1; i < arr.length; i++) {
        reminder = reminder * 2 + arr[i];
        reminder = reminder % 3;
    }
    System.out.println(reminder);
}