fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     static int funnySum(long x, long y) {
  11.         int result = 0;
  12.         for (int i=0; i<32; ++i) {
  13.             int xNum = (int) (x & 3);
  14.             int yNum = (int) (y & 3);
  15.             result += Math.abs(xNum - yNum);
  16.  
  17.             x >>= 2;
  18.             y >>= 2;
  19.         }
  20.         return result;
  21.     }
  22.  
  23.     static int freakySum(long a, long b) {
  24.         long result = a^b;
  25.         long is3 = result & result << 1; //high bit per pair will contain whether the pair is 3
  26.         is3 &= 0xaaaa_aaaa_aaaa_aaaaL; //extract the high bit per pair
  27.         long is0 = a&b;
  28.         is0 = ~(is0 | is0 << 1);//high bit per pair will contain whether the pair is 0
  29.         is0 &= 0xaaaa_aaaa_aaaa_aaaaL; //extract the high bit per pair
  30.         long notBoth0 = ~(a|a<<1) & ~(b|b<<1);
  31.         notBoth0 &= 0xaaaa_aaaa_aaaa_aaaaL; //extract the high bit per pair
  32.         result ^= is3 & is0 & notBoth0; // only invert the bits set in is3, is0 and notBoth0
  33.  
  34.         result = (result & 0x3333_3333_3333_3333L) + ((result >>  2) & 0x3333_3333_3333_3333L);
  35.         result = (result & 0x0f0f_0f0f_0f0f_0f0fL) + ((result >>  4) & 0x0f0f_0f0f_0f0f_0f0fL);
  36.         result = (result & 0x00ff_00ff_00ff_00ffL) + ((result >>  8) & 0x00ff_00ff_00ff_00ffL);
  37.         result = (result & 0x0000_ffff_0000_ffffL) + ((result >> 16) & 0x0000_ffff_0000_ffffL);
  38.         result = (result & 0x0000_0000_ffff_ffffL) + ((result >> 32) & 0x0000_0000_ffff_ffffL);
  39.         return (int)(result&0xffL);
  40.     }
  41.  
  42.     private static final long HIGH = 0xaaaa_aaaa_aaaa_aaaaL;
  43.     static int maaartySum(long x, long y) {
  44.         final long xor = x^y;
  45.         // high bit per pair will contain whether the pair is 3, low bit is garbled
  46.         final long is3 = xor & (xor << 1);
  47.  
  48.         // high bit per pair will contain whether the pair is non-zero, low bit is garbled
  49.         final long x2 = x | (x << 1);
  50.         final long y2 = y | (y << 1);
  51.  
  52.         // high bit per pair will contain whether both pairs are non-zero, low bit is garbled
  53.         final long is0 = x2 & y2;
  54.  
  55.         // high bit per pair will contain whether the pairs need correction, low bit is 0
  56.         final long isBoth = (is3 & is0) & HIGH;
  57.         final long val = xor ^ isBoth; // only invert the bits set in both is3 and is0
  58.  
  59.         // count the high bits twice
  60.         return Long.bitCount(val) + Long.bitCount(val & HIGH);
  61.     }    
  62.  
  63.     private static final long COMP      = 0x1111111111111111L;
  64.     private static final long TWOBITS   = 0x3333333333333333L;
  65.     private static final long THREEBITS = 0x7777777777777777L;
  66.     private static final long SIGNBIT   = 0x4444444444444444L;
  67.     private static final long FOURSET   = 0x0f0f0f0f0f0f0f0fL;
  68.  
  69.  
  70.     static long twoBitDiff(final long x, long y) {
  71.         // two's compliment on 2-bit sets of y - to make 3bit values.
  72.         // third bit is the sign bit.
  73.         y &= TWOBITS;
  74.         y ^= THREEBITS;
  75.         y += COMP;
  76.  
  77.         long diff =  (x & TWOBITS) + y;
  78.  
  79.         // negate any negative results - (abs value)
  80.         // two's complement again
  81.         long sign = (diff & SIGNBIT) >>> 2;
  82.         diff ^= sign | (sign << 1);
  83.         diff += sign;
  84.         return diff & TWOBITS;
  85.  
  86.     }
  87.  
  88.     static int shiftySum(long x, long y) {
  89.  
  90.         long diff = twoBitDiff(x, y) + twoBitDiff(x >>> 2, y >>> 2);
  91.  
  92.         diff += diff >>> 4;
  93.         diff &= FOURSET;
  94.         diff += diff >>> 8;
  95.         diff += diff >>> 16;
  96.         diff += diff >>> 32;
  97.         return (int)(diff & 0xff);
  98.     }
  99.  
  100.     private static final void testSum(long a, long b, boolean always) {
  101.         int fs = funnySum(a, b);
  102.         int ss = shiftySum(a, b);
  103.         int ks = freakySum(a, b);
  104.         int ms = maaartySum(a, b);
  105.         if (fs != ss || fs != ks || fs != ms || always) {
  106.             System.out.printf("%d -> %d funny %d shifty %d freaky %d maaarty %d\n",
  107.                     a, b, funnySum(a, b), shiftySum(a, b), freakySum(a, b), maaartySum(a,b));
  108.         }
  109.     }
  110.  
  111. 	public static void main (String[] args) throws java.lang.Exception
  112. 	{
  113.         testSum(-1, 0, true);
  114.         testSum(0, -1, true);
  115.         testSum(Long.MIN_VALUE, Long.MAX_VALUE, true);
  116.         testSum(Long.MAX_VALUE, 0, true);
  117.         testSum(Long.MIN_VALUE, 0, true);
  118. 	}
  119. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1 -> 0 funny 96 shifty 96 freaky 96 maaarty 96
0 -> -1 funny 96 shifty 96 freaky 96 maaarty 96
-9223372036854775808 -> 9223372036854775807 funny 94 shifty 94 freaky 96 maaarty 94
9223372036854775807 -> 0 funny 94 shifty 94 freaky 94 maaarty 94
-9223372036854775808 -> 0 funny 2 shifty 2 freaky 2 maaarty 2
https://ideone.com/SRIR9a
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!