有效检查数字是否可以被3整除

#1 楼

 public final class DivThreeEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: ifge          7
       4: iload_0       
       5: ineg          
       6: istore_0      
       7: iconst_0      
       8: istore_1      
       9: iconst_0      
      10: istore_2      
      11: iload_0       
      12: ifeq          46
      15: iload_0       
      16: iconst_1      
      17: iand          
      18: iconst_1      
      19: if_icmpne     25
      22: iinc          2, 1
      25: iload_0       
      26: iconst_1      
      27: ishr          
      28: istore_0      
      29: iload_0       
      30: iconst_1      
      31: iand          
      32: iconst_1      
      33: if_icmpne     39
      36: iinc          1, 1
      39: iload_0       
      40: iconst_1      
      41: ishr          
      42: istore_0      
      43: goto          11
      46: iload_1       
      47: iload_2       
      48: if_icmpne     55
      51: iconst_1      
      52: goto          56
      55: iconst_0      
      56: ireturn       
}
 

public class Div3MoreEfficiently {
    private Div3MoreEfficiently() {}

    public static boolean isMultipleOfThree(int n) {
        return n % 3 == 0;
    }
}

 public class Div3MoreEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: iconst_3      
       2: irem          
       3: ifne          10
       6: iconst_1      
       7: goto          11
      10: iconst_0      
      11: ireturn       
}
 

#2 楼

int Q = (n >> 20) + ((n >> 10) & 0x3FF) + (n & 0x3FF);
Q -= ((Q*0x5556) >> 16)*3; // Divide Q by three and then multiply by 3 to get remainder
// Q will be zero if and only if the original number was a multiple of three

if (n<0) n=-n;
int q = (int)((n*0x55555556L) >> 32);
n=n-q-q-q;    
return n==0;

#3 楼

int mask = 0x2AAAAAAA; // special handling for the sign bit
int diff = 2 * Integer.bitCount(x & mask) + Integer.bitCount(x & ~mask);

 return (TABLE << diff) < 0;

private static final long TABLE = 0x9249249249240000L;

int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
return (TABLE << diff) < 0;

#4 楼

for (int i=-100000; i<100000; i++)
    assertEquals(DivThreeEfficiently.isMultipleOfThree(i), i%3==0);

#5 楼

public static boolean isDivisibleByThree(int n) {
    int sum = 0;
    int abs = Math.abs(n);
    if (abs < 10) {
        return abs == 3 || abs == 6 || abs == 9 || abs == 0;
    }
    while (n != 0) {
        sum += n % 10;
        n = n / 10;
    }
    return isDivisibleByThree(sum);
}

#6 楼

import java.util.Arrays;

public class DivisibilityBenchmark {
    static abstract class DivPredicate {
        private final String name;

        public DivPredicate(String name) {
            this.name = name;
        }

        public abstract boolean isMultiple(int n);
    }

    private static final long MAAARTINUS_TABLE = 0x9249249249240000L;
    // = 0b1001001001001001001001001001001001001001001001000000000000000000L;

    private static final DivPredicate[] SOLUTIONS = new DivPredicate[] {
        new DivPredicate("canonical") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        new DivPredicate("200_success") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        new DivPredicate("JavaDeveloper") {
            public boolean isMultiple(int n) {
                if(n < 0) n = -n;

                int evenCtr = 0;
                int oddCtr = 0;

                while (n != 0) {
                    if ((n & 1) == 1) { 
                        oddCtr++;
                    } 
                    n = n>>1;
                    if ((n & 1) == 1) {
                        evenCtr++;
                    } 
                    n = n>>1;
                }

                return evenCtr == oddCtr;
            }
        },

        new DivPredicate("Simon André Forsberg") {
            public boolean isMultiple(int n) {
                int sum = 0;
                int abs = Math.abs(n);
                if (abs < 10) {
                    return abs == 3 || abs == 6 || abs == 9 || abs == 0;
                }
                while (n != 0) {
                    sum += n % 10;
                    n = n / 10;
                }
                return isMultiple(sum);
            }
        },

        new DivPredicate("supercat Rev 2") {
            public boolean isMultiple(int n) {
                int q = (n >> 20) + ((n >> 10) & 0x3ff) + (n & 0x3ff);
                return q == ((q * 0x5556) >> 16) * 3;
            }
        },

        new DivPredicate("supercat Rev 4") {
            public boolean isMultiple(int n) {
                if (n < 0) n = -n;
                int q = (int)((n * 0x55555556L) >> 32);
                n = n - q - q - q;
                return n == 0;
            }
        },

        new DivPredicate("maartinus Rev 4") {
            public boolean isMultiple(int x) {
                int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
                return (MAAARTINUS_TABLE << diff) < 0;
            }
        },

        new DivPredicate("200_success (bis)") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        }
    };

    public static boolean[] run(DivPredicate pred, int lower, int upper) {
        boolean[] results = new boolean[upper - lower];
        for (int i = lower; i < upper; i++) {
            results[i - lower] = pred.isMultiple(i);
        }
        return results;
    }

    public static int perf(DivPredicate pred, int lower, int upper) {
        int count = 0;
        for (int i = lower; i < upper; i++) {
            if (pred.isMultiple(i)) {   // Count results to ensure that the
                count++;                // work is not optimized away
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // Warm-up and correctness tests
        boolean[] expected = null;
        for (DivPredicate pred : SOLUTIONS) {
            boolean[] actual = run(pred, -5000, 5000);
            if (expected == null) {
                expected = actual;
            } else if (!Arrays.equals(expected, actual)) {
                System.out.println("Mismatch " + pred.name);
            }
        }

        // Performance measurement
        final int LOWER = -0x00FFFFFF, UPPER = 0x00FFFFFF;
        for (DivPredicate pred : SOLUTIONS) {
            long start = System.currentTimeMillis();
            perf(pred, LOWER, UPPER);
            long finish = System.currentTimeMillis();
            System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
        }
        for (int i = SOLUTIONS.length - 1; i >= 0; i--) {
            DivPredicate pred = SOLUTIONS[i];
            long start = System.currentTimeMillis();
            perf(pred, LOWER, UPPER);
            long finish = System.currentTimeMillis();
            System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
        }
    }
}

#7 楼

import java.math.BigInteger;

private static final int MULTIPLIER =
  BigInteger.valueOf(3).modInverse(BigInteger.valueOf(2).pow(32)).intValue();
private static final int LOWER_LIMIT = Integer.MIN_VALUE / 3;
private static final int UPPER_LIMIT = Integer.MAX_VALUE / 3;

public static boolean divideFast(int i) {
  int j = i * MULTIPLIER;
  return LOWER_LIMIT <= j && j <= UPPER_LIMIT;
}

#8 楼

private static int reduce(int i) {
    if (i >= 6)
        return reduce((i >> 2) + (i & 0x03));
    else
        return i; // Done.
}

public static boolean isMultipleOfThree(int i) {
    if (i < 0) i = -i;
    // Sum of digits in base 4
    i = (i >> 16) + (i & 0xFFFF);
    i = (i >> 8) + (i & 0xFF);
    i = (i >> 4) + (i & 0xF);
    i = reduce(i);
    return i == 0 || i == 3;
}