import java.util.Set;
import java.util.TreeSet;
/**
*
* "Write a program (in the language of your choice) that takes as input two integers 'a' and 'b' (You can assume that
* the input numbers are non-negative integers bounded to 64 bits). The output should be a single number which is the
* number of integers between 'a' and 'b' (both inclusive), that have Fibonacci number of bits set (in their binary
* representation).
*
* "E.g 000010 : 2 passes the test, 001111: 15 does not pass the test. so between 2 and 15 there are 13 such numbers.
* Run with 1000 = a and 3893942903091930931 = b
*
* Conventional implementations can easily take years to compute the values for large ranges, like the above.
*/
public class FibonacciTest {
public static void main(final String args[]) {
// Accept the number range as command line parameters:
// final long a = Long.parseLong(args[0]);
// final long b = Long.parseLong(args[1]);
// [No; wait -- let's hard code them here.]
final long a = 2;
final long b = 15;
final long count = countNumberWithFibonnaciBitsInRange(a, b);
System.out.println("The count Numbers between given input having fibonnacci binary bit set => " + count);
}
/**
* @param lowValue bottom of test range, inclusive
* @param highValue top of test range, inclusive
* @return the count of numbers from <code>lowValue</code> to <code>testValue</code> inclusive that have, in their binary representation, a number of "1" bits that is a Fibonacci number.
*/
public static long countNumberWithFibonnaciBitsInRange(long lowValue, long highValue) {
if (highValue < lowValue){ //If 2nd number is smaller exchange
final long swapValue = lowValue;
lowValue = highValue;
highValue = swapValue;
}
final long countBelowLowValue = countFibonnaciBitsUpToAndIncluding(lowValue - 1);
final long countToHighValue = countFibonnaciBitsUpToAndIncluding(highValue);
return countToHighValue - countBelowLowValue;
}
/**
* @param testValue high value of range, inclusive
* @return the count of numbers from zero up to and including <code>testValue</code> that have, in their binary representation, a number of "1" bits that is a Fibonacci number.
*/
public static long countFibonnaciBitsUpToAndIncluding(long testValue) {
long countForTestValue = 0;
// Even numbers get special treatment, to get us to an odd number:
if (testValue > 0 && testValue % 2 == 0) {
if (hasFibonacciBitsSet(testValue)) {
++countForTestValue;
}
--testValue;
}
// Because this algorithm only works for odd numbers:
while (testValue > 0) {
// Isolate the group of trailing "1" bits at the end by taking advantage of the way that carry works when adding one:
final long trailingOneBits = (testValue ^ (testValue + 1)) / 2;
final int numberOfTrailingOneBits = Long.bitCount(trailingOneBits);
final long lowValue = testValue - trailingOneBits; // Range being considered is [lowValue, testValue], inclusive.
final int leadingOneBits = Long.bitCount(lowValue); // = countForTestValue of all "1" bits to the left of the group on the right that we're focused on.
for (final int fibonnaciNumber : FIBONNACI_NUMBERS_TO_64) {
final int remainingOneBitsToUse = fibonnaciNumber - leadingOneBits; // Bits left to populate the "trailingOneBits" locations.
if (remainingOneBitsToUse < 0) {
continue; // to next Fibonacci number.
} else if (remainingOneBitsToUse > numberOfTrailingOneBits) {
break; // as this and all remaining Fibonacci numbers are all too large.
} else {
// Combination of numberOfTrailingOneBits bits, taken remainingOneBitsToUse at a time.
final int remainingZeroBitsToUse = numberOfTrailingOneBits - remainingOneBitsToUse;
final long countForThisRangeAndFibonacciNumber = combinationsOfXBitsTakenYAtATime[numberOfTrailingOneBits][Math.min(remainingOneBitsToUse, remainingZeroBitsToUse)];
countForTestValue += countForThisRangeAndFibonacciNumber;
if (countForTestValue < 0) {
throw new NumberFormatException("Overflow!!!");
}
}
}
testValue = lowValue - 1;
}
return countForTestValue;
}
/**
* @param testValue numeric value to test
* @return <code>true</code> if the number of "1" bits in the binary representation of <code>testValue</code> is a number in the Fibonacci sequence.
*/
/* package */ static boolean hasFibonacciBitsSet(final long testValue) {
//Function which counts number of set Bits
final int numOfSetBits = Long.bitCount(testValue);
//Check if its fibonacci number
return FIBONNACI_NUMBER_FLAGS_TO_64[numOfSetBits];
}
/**
* @param maxValue largest value allowed in the resulting Set.
* @return an ordered Set of Integer values from the Figonacci sequence between 1 and the given maximum value, inclusive.
*/
/* package */ static TreeSet<Integer> computeFibonacciNumbers(final int maxValue) {
final TreeSet<Integer> fibs = new TreeSet<Integer>();
int previousValue = 0;
int currentValue = 1;
while (currentValue <= maxValue) {
fibs.add(currentValue);
final int nextValue = previousValue + currentValue;
previousValue = currentValue;
currentValue = nextValue;
}
return fibs;
}
/**
* Given a Set of Fibonacci numbers from 1 to <code>topValue</code>, generate and return an array of Boolean flags
* in the range of zero to <code>topValue</code>, with the value <code>true</code> for indexes that hae Fibonnaci
* number values; <code>false</code> for others.
* @param fibonacciNumbers a Set of Fibonacci numbers from 1 to <code>topValue</code>
* @param topValue largest index of the resulting array
* @return an array of Boolean flags in the range of zero to <code>topValue</code>, with the value <code>true</code> for indexes that hae Fibonnaci number values; <code>false</code> for others.
*/
private static boolean[] generateFibonnaciNumberFlags(final Set<Integer> fibonacciNumbers, final int topValue) {
final boolean[] flags = new boolean[topValue + 1];
for (int value = 0; value <= topValue; ++value) {
flags[value] = fibonacciNumbers.contains(value);
}
return flags;
}
/* package */ static final TreeSet<Integer> FIBONNACI_NUMBERS_TO_64 = computeFibonacciNumbers(Long.SIZE);
/* package */ static final boolean[] FIBONNACI_NUMBER_FLAGS_TO_64 = generateFibonnaciNumberFlags(FIBONNACI_NUMBERS_TO_64, Long.SIZE);
/* package */ static final long[][] combinationsOfXBitsTakenYAtATime = {
/* 0 */ {1L},
/* 1 */ {1L, 1L},
/* 2 */ {1L, 2L},
/* 3 */ {1L, 3L, 3L},
/* 4 */ {1L, 4L, 6L},
/* 5 */ {1L, 5L, 10L, 10L},
/* 6 */ {1L, 6L, 15L, 20L},
/* 7 */ {1L, 7L, 21L, 35L, 35L},
/* 8 */ {1L, 8L, 28L, 56L, 70L},
/* 9 */ {1L, 9L, 36L, 84L, 126L, 126L},
/* 10 */ {1L, 10L, 45L, 120L, 210L, 252L},
/* 11 */ {1L, 11L, 55L, 165L, 330L, 462L, 462L},
/* 12 */ {1L, 12L, 66L, 220L, 495L, 792L, 924L},
/* 13 */ {1L, 13L, 78L, 286L, 715L, 1287L, 1716L, 1716L},
/* 14 */ {1L, 14L, 91L, 364L, 1001L, 2002L, 3003L, 3432L},
/* 15 */ {1L, 15L, 105L, 455L, 1365L, 3003L, 5005L, 6435L, 6435L},
/* 16 */ {1L, 16L, 120L, 560L, 1820L, 4368L, 8008L, 11440L, 12870L},
/* 17 */ {1L, 17L, 136L, 680L, 2380L, 6188L, 12376L, 19448L, 24310L, 24310L},
/* 18 */ {1L, 18L, 153L, 816L, 3060L, 8568L, 18564L, 31824L, 43758L, 48620L},
/* 19 */ {1L, 19L, 171L, 969L, 3876L, 11628L, 27132L, 50388L, 75582L, 92378L, 92378L},
/* 20 */ {1L, 20L, 190L, 1140L, 4845L, 15504L, 38760L, 77520L, 125970L, 167960L, 184756L},
/* 21 */ {1L, 21L, 210L, 1330L, 5985L, 20349L, 54264L, 116280L, 203490L, 293930L, 352716L, 352716L},
/* 22 */ {1L, 22L, 231L, 1540L, 7315L, 26334L, 74613L, 170544L, 319770L, 497420L, 646646L, 705432L},
/* 23 */ {1L, 23L, 253L, 1771L, 8855L, 33649L, 100947L, 245157L, 490314L, 817190L, 1144066L, 1352078L, 1352078L},
/* 24 */ {1L, 24L, 276L, 2024L, 10626L, 42504L, 134596L, 346104L, 735471L, 1307504L, 1961256L, 2496144L, 2704156L},
/* 25 */ {1L, 25L, 300L, 2300L, 12650L, 53130L, 177100L, 480700L, 1081575L, 2042975L, 3268760L, 4457400L, 5200300L, 5200300L},
/* 26 */ {1L, 26L, 325L, 2600L, 14950L, 65780L, 230230L, 657800L, 1562275L, 3124550L, 5311735L, 7726160L, 9657700L, 10400600L},
/* 27 */ {1L, 27L, 351L, 2925L, 17550L, 80730L, 296010L, 888030L, 2220075L, 4686825L, 8436285L, 13037895L, 17383860L, 20058300L, 20058300L},
/* 28 */ {1L, 28L, 378L, 3276L, 20475L, 98280L, 376740L, 1184040L, 3108105L, 6906900L, 13123110L, 21474180L, 30421755L, 37442160L, 40116600L},
/* 29 */ {1L, 29L, 406L, 3654L, 23751L, 118755L, 475020L, 1560780L, 4292145L, 10015005L, 20030010L, 34597290L, 51895935L, 67863915L, 77558760L, 77558760L},
/* 30 */ {1L, 30L, 435L, 4060L, 27405L, 142506L, 593775L, 2035800L, 5852925L, 14307150L, 30045015L, 54627300L, 86493225L, 119759850L, 145422675L, 155117520L},
/* 31 */ {1L, 31L, 465L, 4495L, 31465L, 169911L, 736281L, 2629575L, 7888725L, 20160075L, 44352165L, 84672315L, 141120525L, 206253075L, 265182525L, 300540195L, 300540195L},
/* 32 */ {1L, 32L, 496L, 4960L, 35960L, 201376L, 906192L, 3365856L, 10518300L, 28048800L, 64512240L, 129024480L, 225792840L, 347373600L, 471435600L, 565722720L, 601080390L},
/* 33 */ {1L, 33L, 528L, 5456L, 40920L, 237336L, 1107568L, 4272048L, 13884156L, 38567100L, 92561040L, 193536720L, 354817320L, 573166440L, 818809200L, 1037158320L, 1166803110L, 1166803110L},
/* 34 */ {1L, 34L, 561L, 5984L, 46376L, 278256L, 1344904L, 5379616L, 18156204L, 52451256L, 131128140L, 286097760L, 548354040L, 927983760L, 1391975640L, 1855967520L, 2203961430L, 2333606220L},
/* 35 */ {1L, 35L, 595L, 6545L, 52360L, 324632L, 1623160L, 6724520L, 23535820L, 70607460L, 183579396L, 417225900L, 834451800L, 1476337800L, 2319959400L, 3247943160L, 4059928950L, 4537567650L, 4537567650L},
/* 36 */ {1L, 36L, 630L, 7140L, 58905L, 376992L, 1947792L, 8347680L, 30260340L, 94143280L, 254186856L, 600805296L, 1251677700L, 2310789600L, 3796297200L, 5567902560L, 7307872110L, 8597496600L, 9075135300L},
/* 37 */ {1L, 37L, 666L, 7770L, 66045L, 435897L, 2324784L, 10295472L, 38608020L, 124403620L, 348330136L, 854992152L, 1852482996L, 3562467300L, 6107086800L, 9364199760L, 12875774670L, 15905368710L, 17672631900L, 17672631900L},
/* 38 */ {1L, 38L, 703L, 8436L, 73815L, 501942L, 2760681L, 12620256L, 48903492L, 163011640L, 472733756L, 1203322288L, 2707475148L, 5414950296L, 9669554100L, 15471286560L, 22239974430L, 28781143380L, 33578000610L, 35345263800L},
/* 39 */ {1L, 39L, 741L, 9139L, 82251L, 575757L, 3262623L, 15380937L, 61523748L, 211915132L, 635745396L, 1676056044L, 3910797436L, 8122425444L, 15084504396L, 25140840660L, 37711260990L, 51021117810L, 62359143990L, 68923264410L, 68923264410L},
/* 40 */ {1L, 40L, 780L, 9880L, 91390L, 658008L, 3838380L, 18643560L, 76904685L, 273438880L, 847660528L, 2311801440L, 5586853480L, 12033222880L, 23206929840L, 40225345056L, 62852101650L, 88732378800L, 113380261800L, 131282408400L, 137846528820L},
/* 41 */ {1L, 41L, 820L, 10660L, 101270L, 749398L, 4496388L, 22481940L, 95548245L, 350343565L, 1121099408L, 3159461968L, 7898654920L, 17620076360L, 35240152720L, 63432274896L, 103077446706L, 151584480450L, 202112640600L, 244662670200L, 269128937220L, 269128937220L},
/* 42 */ {1L, 42L, 861L, 11480L, 111930L, 850668L, 5245786L, 26978328L, 118030185L, 445891810L, 1471442973L, 4280561376L, 11058116888L, 25518731280L, 52860229080L, 98672427616L, 166509721602L, 254661927156L, 353697121050L, 446775310800L, 513791607420L, 538257874440L},
/* 43 */ {1L, 43L, 903L, 12341L, 123410L, 962598L, 6096454L, 32224114L, 145008513L, 563921995L, 1917334783L, 5752004349L, 15338678264L, 36576848168L, 78378960360L, 151532656696L, 265182149218L, 421171648758L, 608359048206L, 800472431850L, 960566918220L, 1052049481860L, 1052049481860L},
/* 44 */ {1L, 44L, 946L, 13244L, 135751L, 1086008L, 7059052L, 38320568L, 177232627L, 708930508L, 2481256778L, 7669339132L, 21090682613L, 51915526432L, 114955808528L, 229911617056L, 416714805914L, 686353797976L, 1029530696964L, 1408831480056L, 1761039350070L, 2012616400080L, 2104098963720L},
/* 45 */ {1L, 45L, 990L, 14190L, 148995L, 1221759L, 8145060L, 45379620L, 215553195L, 886163135L, 3190187286L, 10150595910L, 28760021745L, 73006209045L, 166871334960L, 344867425584L, 646626422970L, 1103068603890L, 1715884494940L, 2438362177020L, 3169870830126L, 3773655750150L, 4116715363800L, 4116715363800L},
/* 46 */ {1L, 46L, 1035L, 15180L, 163185L, 1370754L, 9366819L, 53524680L, 260932815L, 1101716330L, 4076350421L, 13340783196L, 38910617655L, 101766230790L, 239877544005L, 511738760544L, 991493848554L, 1749695026860L, 2818953098830L, 4154246671960L, 5608233007146L, 6943526580276L, 7890371113950L, 8233430727600L},
/* 47 */ {1L, 47L, 1081L, 16215L, 178365L, 1533939L, 10737573L, 62891499L, 314457495L, 1362649145L, 5178066751L, 17417133617L, 52251400851L, 140676848445L, 341643774795L, 751616304549L, 1503232609098L, 2741188875414L, 4568648125690L, 6973199770790L, 9762479679106L, 12551759587422L, 14833897694226L, 16123801841550L, 16123801841550L},
/* 48 */ {1L, 48L, 1128L, 17296L, 194580L, 1712304L, 12271512L, 73629072L, 377348994L, 1677106640L, 6540715896L, 22595200368L, 69668534468L, 192928249296L, 482320623240L, 1093260079344L, 2254848913647L, 4244421484512L, 7309837001104L, 11541847896480L, 16735679449896L, 22314239266528L, 27385657281648L, 30957699535776L, 32247603683100L},
/* 49 */ {1L, 49L, 1176L, 18424L, 211876L, 1906884L, 13983816L, 85900584L, 450978066L, 2054455634L, 8217822536L, 29135916264L, 92263734836L, 262596783764L, 675248872536L, 1575580702584L, 3348108992991L, 6499270398159L, 11554258485616L, 18851684897584L, 28277527346376L, 39049918716424L, 49699896548176L, 58343356817424L, 63205303218876L, 63205303218876L},
/* 50 */ {1L, 50L, 1225L, 19600L, 230300L, 2118760L, 15890700L, 99884400L, 536878650L, 2505433700L, 10272278170L, 37353738800L, 121399651100L, 354860518600L, 937845656300L, 2250829575120L, 4923689695575L, 9847379391150L, 18053528883775L, 30405943383200L, 47129212243960L, 67327446062800L, 88749815264600L, 108043253365600L, 121548660036300L, 126410606437752L},
/* 51 */ {1L, 51L, 1275L, 20825L, 249900L, 2349060L, 18009460L, 115775100L, 636763050L, 3042312350L, 12777711870L, 47626016970L, 158753389900L, 476260169700L, 1292706174900L, 3188675231420L, 7174519270695L, 14771069086725L, 27900908274925L, 48459472266975L, 77535155627160L, 114456658306760L, 156077261327400L, 196793068630200L, 229591913401900L, 247959266474052L, 247959266474052L},
/* 52 */ {1L, 52L, 1326L, 22100L, 270725L, 2598960L, 20358520L, 133784560L, 752538150L, 3679075400L, 15820024220L, 60403728840L, 206379406870L, 635013559600L, 1768966344600L, 4481381406320L, 10363194502115L, 21945588357420L, 42671977361650L, 76360380541900L, 125994627894135L, 191991813933920L, 270533919634160L, 352870329957600L, 426384982032100L, 477551179875952L, 495918532948104L},
/* 53 */ {1L, 53L, 1378L, 23426L, 292825L, 2869685L, 22957480L, 154143080L, 886322710L, 4431613550L, 19499099620L, 76223753060L, 266783135710L, 841392966470L, 2403979904200L, 6250347750920L, 14844575908435L, 32308782859535L, 64617565719070L, 119032357903550L, 202355008436035L, 317986441828055L, 462525733568080L, 623404249591760L, 779255311989700L, 903936161908052L, 973469712824056L, 973469712824056L},
/* 54 */ {1L, 54L, 1431L, 24804L, 316251L, 3162510L, 25827165L, 177100560L, 1040465790L, 5317936260L, 23930713170L, 95722852680L, 343006888770L, 1108176102180L, 3245372870670L, 8654327655120L, 21094923659355L, 47153358767970L, 96926348578605L, 183649923622620L, 321387366339585L, 520341450264090L, 780512175396135L, 1085929983159840L, 1402659561581460L, 1683191473897752L, 1877405874732108L, 1946939425648112L},
/* 55 */ {1L, 55L, 1485L, 26235L, 341055L, 3478761L, 28989675L, 202927725L, 1217566350L, 6358402050L, 29248649430L, 119653565850L, 438729741450L, 1451182990950L, 4353548972850L, 11899700525790L, 29749251314475L, 68248282427325L, 144079707346575L, 280576272201225L, 505037289962205L, 841728816603675L, 1300853625660225L, 1866442158555975L, 2488589544741300L, 3085851035479212L, 3560597348629860L, 3824345300380220L, 3824345300380220L},
/* 56 */ {1L, 56L, 1540L, 27720L, 367290L, 3819816L, 32468436L, 231917400L, 1420494075L, 7575968400L, 35607051480L, 148902215280L, 558383307300L, 1889912732400L, 5804731963800L, 16253249498640L, 41648951840265L, 97997533741800L, 212327989773900L, 424655979547800L, 785613562163430L, 1346766106565880L, 2142582442263900L, 3167295784216200L, 4355031703297275L, 5574440580220512L, 6646448384109072L, 7384942649010080L, 7648690600760440L},
/* 57 */ {1L, 57L, 1596L, 29260L, 395010L, 4187106L, 36288252L, 264385836L, 1652411475L, 8996462475L, 43183019880L, 184509266760L, 707285522580L, 2448296039700L, 7694644696200L, 22057981462440L, 57902201338905L, 139646485582065L, 310325523515700L, 636983969321700L, 1210269541711230L, 2132379668729310L, 3489348548829780L, 5309878226480100L, 7522327487513475L, 9929472283517787L, 12220888964329584L, 14031391033119152L, 15033633249770520L, 15033633249770520L},
/* 58 */ {1L, 58L, 1653L, 30856L, 424270L, 4582116L, 40475358L, 300674088L, 1916797311L, 10648873950L, 52179482355L, 227692286640L, 891794789340L, 3155581562280L, 10142940735900L, 29752626158640L, 79960182801345L, 197548686920970L, 449972009097765L, 947309492837400L, 1847253511032930L, 3342649210440540L, 5621728217559090L, 8799226775309880L, 12832205713993575L, 17451799771031262L, 22150361247847371L, 26252279997448736L, 29065024282889672L, 30067266499541040L},
/* 59 */ {1L, 59L, 1711L, 32509L, 455126L, 5006386L, 45057474L, 341149446L, 2217471399L, 12565671261L, 62828356305L, 279871768995L, 1119487075980L, 4047376351620L, 13298522298180L, 39895566894540L, 109712808959985L, 277508869722315L, 647520696018735L, 1397281501935165L, 2794563003870330L, 5189902721473470L, 8964377427999630L, 14420954992868970L, 21631432489303455L, 30284005485024837L, 39602161018878633L, 48402641245296107L, 55317304280338408L, 59132290782430712L, 59132290782430712L},
/* 60 */ {1L, 60L, 1770L, 34220L, 487635L, 5461512L, 50063860L, 386206920L, 2558620845L, 14783142660L, 75394027566L, 342700125300L, 1399358844975L, 5166863427600L, 17345898649800L, 53194089192720L, 149608375854525L, 387221678682300L, 925029565741050L, 2044802197953900L, 4191844505805495L, 7984465725343800L, 14154280149473100L, 23385332420868600L, 36052387482172425L, 51915437974328292L, 69886166503903470L, 88004802264174740L, 103719945525634515L, 114449595062769120L, 118264581564861424L},
/* 61 */ {1L, 61L, 1830L, 35990L, 521855L, 5949147L, 55525372L, 436270780L, 2944827765L, 17341763505L, 90177170226L, 418094152866L, 1742058970275L, 6566222272575L, 22512762077400L, 70539987842520L, 202802465047245L, 536830054536825L, 1312251244423350L, 2969831763694950L, 6236646703759395L, 12176310231149295L, 22138745874816900L, 37539612570341700L, 59437719903041025L, 87967825456500717L, 121801604478231762L, 157890968768078210L, 191724747789809255L, 218169540588403635L, 232714176627630544L, 232714176627630544L},
/* 62 */ {1L, 62L, 1891L, 37820L, 557845L, 6471002L, 61474519L, 491796152L, 3381098545L, 20286591270L, 107518933731L, 508271323092L, 2160153123141L, 8308281242850L, 29078984349975L, 93052749919920L, 273342452889765L, 739632519584070L, 1849081298960175L, 4282083008118300L, 9206478467454345L, 18412956934908690L, 34315056105966195L, 59678358445158600L, 96977332473382725L, 147405545359541742L, 209769429934732479L, 279692573246309972L, 349615716557887465L, 409894288378212890L, 450883717216034179L, 465428353255261088L},
/* 63 */ {1L, 63L, 1953L, 39711L, 595665L, 7028847L, 67945521L, 553270671L, 3872894697L, 23667689815L, 127805525001L, 615790256823L, 2668424446233L, 10468434365991L, 37387265592825L, 122131734269895L, 366395202809685L, 1012974972473835L, 2588713818544245L, 6131164307078475L, 13488561475572645L, 27619435402363035L, 52728013040874885L, 93993414551124795L, 156655690918541325L, 244382877832924467L, 357174975294274221L, 489462003181042451L, 629308289804197437L, 759510004936100355L, 860778005594247069L, 916312070471295267L, 916312070471295267L},
/* 64 */ {1L, 64L, 2016L, 41664L, 635376L, 7624512L, 74974368L, 621216192L, 4426165368L, 27540584512L, 151473214816L, 743595781824L, 3284214703056L, 13136858812224L, 47855699958816L, 159518999862720L, 488526937079580L, 1379370175283520L, 3601688791018080L, 8719878125622720L, 19619725782651120L, 41107996877935680L, 80347448443237920L, 146721427591999680L, 250649105469666120L, 401038568751465792L, 601557853127198688L, 846636978475316672L, 1118770292985239888L, 1388818294740297792L, 1620288010530347424L, 1777090076065542336L, 1832624140942590534L}
};
}
import java.util.TreeSet;
/**
*
* "Write a program (in the language of your choice) that takes as input two integers 'a' and 'b' (You can assume that
* the input numbers are non-negative integers bounded to 64 bits). The output should be a single number which is the
* number of integers between 'a' and 'b' (both inclusive), that have Fibonacci number of bits set (in their binary
* representation).
*
* "E.g 000010 : 2 passes the test, 001111: 15 does not pass the test. so between 2 and 15 there are 13 such numbers.
* Run with 1000 = a and 3893942903091930931 = b
*
* Conventional implementations can easily take years to compute the values for large ranges, like the above.
*/
public class FibonacciTest {
public static void main(final String args[]) {
// Accept the number range as command line parameters:
// final long a = Long.parseLong(args[0]);
// final long b = Long.parseLong(args[1]);
// [No; wait -- let's hard code them here.]
final long a = 2;
final long b = 15;
final long count = countNumberWithFibonnaciBitsInRange(a, b);
System.out.println("The count Numbers between given input having fibonnacci binary bit set => " + count);
}
/**
* @param lowValue bottom of test range, inclusive
* @param highValue top of test range, inclusive
* @return the count of numbers from <code>lowValue</code> to <code>testValue</code> inclusive that have, in their binary representation, a number of "1" bits that is a Fibonacci number.
*/
public static long countNumberWithFibonnaciBitsInRange(long lowValue, long highValue) {
if (highValue < lowValue){ //If 2nd number is smaller exchange
final long swapValue = lowValue;
lowValue = highValue;
highValue = swapValue;
}
final long countBelowLowValue = countFibonnaciBitsUpToAndIncluding(lowValue - 1);
final long countToHighValue = countFibonnaciBitsUpToAndIncluding(highValue);
return countToHighValue - countBelowLowValue;
}
/**
* @param testValue high value of range, inclusive
* @return the count of numbers from zero up to and including <code>testValue</code> that have, in their binary representation, a number of "1" bits that is a Fibonacci number.
*/
public static long countFibonnaciBitsUpToAndIncluding(long testValue) {
long countForTestValue = 0;
// Even numbers get special treatment, to get us to an odd number:
if (testValue > 0 && testValue % 2 == 0) {
if (hasFibonacciBitsSet(testValue)) {
++countForTestValue;
}
--testValue;
}
// Because this algorithm only works for odd numbers:
while (testValue > 0) {
// Isolate the group of trailing "1" bits at the end by taking advantage of the way that carry works when adding one:
final long trailingOneBits = (testValue ^ (testValue + 1)) / 2;
final int numberOfTrailingOneBits = Long.bitCount(trailingOneBits);
final long lowValue = testValue - trailingOneBits; // Range being considered is [lowValue, testValue], inclusive.
final int leadingOneBits = Long.bitCount(lowValue); // = countForTestValue of all "1" bits to the left of the group on the right that we're focused on.
for (final int fibonnaciNumber : FIBONNACI_NUMBERS_TO_64) {
final int remainingOneBitsToUse = fibonnaciNumber - leadingOneBits; // Bits left to populate the "trailingOneBits" locations.
if (remainingOneBitsToUse < 0) {
continue; // to next Fibonacci number.
} else if (remainingOneBitsToUse > numberOfTrailingOneBits) {
break; // as this and all remaining Fibonacci numbers are all too large.
} else {
// Combination of numberOfTrailingOneBits bits, taken remainingOneBitsToUse at a time.
final int remainingZeroBitsToUse = numberOfTrailingOneBits - remainingOneBitsToUse;
final long countForThisRangeAndFibonacciNumber = combinationsOfXBitsTakenYAtATime[numberOfTrailingOneBits][Math.min(remainingOneBitsToUse, remainingZeroBitsToUse)];
countForTestValue += countForThisRangeAndFibonacciNumber;
if (countForTestValue < 0) {
throw new NumberFormatException("Overflow!!!");
}
}
}
testValue = lowValue - 1;
}
return countForTestValue;
}
/**
* @param testValue numeric value to test
* @return <code>true</code> if the number of "1" bits in the binary representation of <code>testValue</code> is a number in the Fibonacci sequence.
*/
/* package */ static boolean hasFibonacciBitsSet(final long testValue) {
//Function which counts number of set Bits
final int numOfSetBits = Long.bitCount(testValue);
//Check if its fibonacci number
return FIBONNACI_NUMBER_FLAGS_TO_64[numOfSetBits];
}
/**
* @param maxValue largest value allowed in the resulting Set.
* @return an ordered Set of Integer values from the Figonacci sequence between 1 and the given maximum value, inclusive.
*/
/* package */ static TreeSet<Integer> computeFibonacciNumbers(final int maxValue) {
final TreeSet<Integer> fibs = new TreeSet<Integer>();
int previousValue = 0;
int currentValue = 1;
while (currentValue <= maxValue) {
fibs.add(currentValue);
final int nextValue = previousValue + currentValue;
previousValue = currentValue;
currentValue = nextValue;
}
return fibs;
}
/**
* Given a Set of Fibonacci numbers from 1 to <code>topValue</code>, generate and return an array of Boolean flags
* in the range of zero to <code>topValue</code>, with the value <code>true</code> for indexes that hae Fibonnaci
* number values; <code>false</code> for others.
* @param fibonacciNumbers a Set of Fibonacci numbers from 1 to <code>topValue</code>
* @param topValue largest index of the resulting array
* @return an array of Boolean flags in the range of zero to <code>topValue</code>, with the value <code>true</code> for indexes that hae Fibonnaci number values; <code>false</code> for others.
*/
private static boolean[] generateFibonnaciNumberFlags(final Set<Integer> fibonacciNumbers, final int topValue) {
final boolean[] flags = new boolean[topValue + 1];
for (int value = 0; value <= topValue; ++value) {
flags[value] = fibonacciNumbers.contains(value);
}
return flags;
}
/* package */ static final TreeSet<Integer> FIBONNACI_NUMBERS_TO_64 = computeFibonacciNumbers(Long.SIZE);
/* package */ static final boolean[] FIBONNACI_NUMBER_FLAGS_TO_64 = generateFibonnaciNumberFlags(FIBONNACI_NUMBERS_TO_64, Long.SIZE);
/* package */ static final long[][] combinationsOfXBitsTakenYAtATime = {
/* 0 */ {1L},
/* 1 */ {1L, 1L},
/* 2 */ {1L, 2L},
/* 3 */ {1L, 3L, 3L},
/* 4 */ {1L, 4L, 6L},
/* 5 */ {1L, 5L, 10L, 10L},
/* 6 */ {1L, 6L, 15L, 20L},
/* 7 */ {1L, 7L, 21L, 35L, 35L},
/* 8 */ {1L, 8L, 28L, 56L, 70L},
/* 9 */ {1L, 9L, 36L, 84L, 126L, 126L},
/* 10 */ {1L, 10L, 45L, 120L, 210L, 252L},
/* 11 */ {1L, 11L, 55L, 165L, 330L, 462L, 462L},
/* 12 */ {1L, 12L, 66L, 220L, 495L, 792L, 924L},
/* 13 */ {1L, 13L, 78L, 286L, 715L, 1287L, 1716L, 1716L},
/* 14 */ {1L, 14L, 91L, 364L, 1001L, 2002L, 3003L, 3432L},
/* 15 */ {1L, 15L, 105L, 455L, 1365L, 3003L, 5005L, 6435L, 6435L},
/* 16 */ {1L, 16L, 120L, 560L, 1820L, 4368L, 8008L, 11440L, 12870L},
/* 17 */ {1L, 17L, 136L, 680L, 2380L, 6188L, 12376L, 19448L, 24310L, 24310L},
/* 18 */ {1L, 18L, 153L, 816L, 3060L, 8568L, 18564L, 31824L, 43758L, 48620L},
/* 19 */ {1L, 19L, 171L, 969L, 3876L, 11628L, 27132L, 50388L, 75582L, 92378L, 92378L},
/* 20 */ {1L, 20L, 190L, 1140L, 4845L, 15504L, 38760L, 77520L, 125970L, 167960L, 184756L},
/* 21 */ {1L, 21L, 210L, 1330L, 5985L, 20349L, 54264L, 116280L, 203490L, 293930L, 352716L, 352716L},
/* 22 */ {1L, 22L, 231L, 1540L, 7315L, 26334L, 74613L, 170544L, 319770L, 497420L, 646646L, 705432L},
/* 23 */ {1L, 23L, 253L, 1771L, 8855L, 33649L, 100947L, 245157L, 490314L, 817190L, 1144066L, 1352078L, 1352078L},
/* 24 */ {1L, 24L, 276L, 2024L, 10626L, 42504L, 134596L, 346104L, 735471L, 1307504L, 1961256L, 2496144L, 2704156L},
/* 25 */ {1L, 25L, 300L, 2300L, 12650L, 53130L, 177100L, 480700L, 1081575L, 2042975L, 3268760L, 4457400L, 5200300L, 5200300L},
/* 26 */ {1L, 26L, 325L, 2600L, 14950L, 65780L, 230230L, 657800L, 1562275L, 3124550L, 5311735L, 7726160L, 9657700L, 10400600L},
/* 27 */ {1L, 27L, 351L, 2925L, 17550L, 80730L, 296010L, 888030L, 2220075L, 4686825L, 8436285L, 13037895L, 17383860L, 20058300L, 20058300L},
/* 28 */ {1L, 28L, 378L, 3276L, 20475L, 98280L, 376740L, 1184040L, 3108105L, 6906900L, 13123110L, 21474180L, 30421755L, 37442160L, 40116600L},
/* 29 */ {1L, 29L, 406L, 3654L, 23751L, 118755L, 475020L, 1560780L, 4292145L, 10015005L, 20030010L, 34597290L, 51895935L, 67863915L, 77558760L, 77558760L},
/* 30 */ {1L, 30L, 435L, 4060L, 27405L, 142506L, 593775L, 2035800L, 5852925L, 14307150L, 30045015L, 54627300L, 86493225L, 119759850L, 145422675L, 155117520L},
/* 31 */ {1L, 31L, 465L, 4495L, 31465L, 169911L, 736281L, 2629575L, 7888725L, 20160075L, 44352165L, 84672315L, 141120525L, 206253075L, 265182525L, 300540195L, 300540195L},
/* 32 */ {1L, 32L, 496L, 4960L, 35960L, 201376L, 906192L, 3365856L, 10518300L, 28048800L, 64512240L, 129024480L, 225792840L, 347373600L, 471435600L, 565722720L, 601080390L},
/* 33 */ {1L, 33L, 528L, 5456L, 40920L, 237336L, 1107568L, 4272048L, 13884156L, 38567100L, 92561040L, 193536720L, 354817320L, 573166440L, 818809200L, 1037158320L, 1166803110L, 1166803110L},
/* 34 */ {1L, 34L, 561L, 5984L, 46376L, 278256L, 1344904L, 5379616L, 18156204L, 52451256L, 131128140L, 286097760L, 548354040L, 927983760L, 1391975640L, 1855967520L, 2203961430L, 2333606220L},
/* 35 */ {1L, 35L, 595L, 6545L, 52360L, 324632L, 1623160L, 6724520L, 23535820L, 70607460L, 183579396L, 417225900L, 834451800L, 1476337800L, 2319959400L, 3247943160L, 4059928950L, 4537567650L, 4537567650L},
/* 36 */ {1L, 36L, 630L, 7140L, 58905L, 376992L, 1947792L, 8347680L, 30260340L, 94143280L, 254186856L, 600805296L, 1251677700L, 2310789600L, 3796297200L, 5567902560L, 7307872110L, 8597496600L, 9075135300L},
/* 37 */ {1L, 37L, 666L, 7770L, 66045L, 435897L, 2324784L, 10295472L, 38608020L, 124403620L, 348330136L, 854992152L, 1852482996L, 3562467300L, 6107086800L, 9364199760L, 12875774670L, 15905368710L, 17672631900L, 17672631900L},
/* 38 */ {1L, 38L, 703L, 8436L, 73815L, 501942L, 2760681L, 12620256L, 48903492L, 163011640L, 472733756L, 1203322288L, 2707475148L, 5414950296L, 9669554100L, 15471286560L, 22239974430L, 28781143380L, 33578000610L, 35345263800L},
/* 39 */ {1L, 39L, 741L, 9139L, 82251L, 575757L, 3262623L, 15380937L, 61523748L, 211915132L, 635745396L, 1676056044L, 3910797436L, 8122425444L, 15084504396L, 25140840660L, 37711260990L, 51021117810L, 62359143990L, 68923264410L, 68923264410L},
/* 40 */ {1L, 40L, 780L, 9880L, 91390L, 658008L, 3838380L, 18643560L, 76904685L, 273438880L, 847660528L, 2311801440L, 5586853480L, 12033222880L, 23206929840L, 40225345056L, 62852101650L, 88732378800L, 113380261800L, 131282408400L, 137846528820L},
/* 41 */ {1L, 41L, 820L, 10660L, 101270L, 749398L, 4496388L, 22481940L, 95548245L, 350343565L, 1121099408L, 3159461968L, 7898654920L, 17620076360L, 35240152720L, 63432274896L, 103077446706L, 151584480450L, 202112640600L, 244662670200L, 269128937220L, 269128937220L},
/* 42 */ {1L, 42L, 861L, 11480L, 111930L, 850668L, 5245786L, 26978328L, 118030185L, 445891810L, 1471442973L, 4280561376L, 11058116888L, 25518731280L, 52860229080L, 98672427616L, 166509721602L, 254661927156L, 353697121050L, 446775310800L, 513791607420L, 538257874440L},
/* 43 */ {1L, 43L, 903L, 12341L, 123410L, 962598L, 6096454L, 32224114L, 145008513L, 563921995L, 1917334783L, 5752004349L, 15338678264L, 36576848168L, 78378960360L, 151532656696L, 265182149218L, 421171648758L, 608359048206L, 800472431850L, 960566918220L, 1052049481860L, 1052049481860L},
/* 44 */ {1L, 44L, 946L, 13244L, 135751L, 1086008L, 7059052L, 38320568L, 177232627L, 708930508L, 2481256778L, 7669339132L, 21090682613L, 51915526432L, 114955808528L, 229911617056L, 416714805914L, 686353797976L, 1029530696964L, 1408831480056L, 1761039350070L, 2012616400080L, 2104098963720L},
/* 45 */ {1L, 45L, 990L, 14190L, 148995L, 1221759L, 8145060L, 45379620L, 215553195L, 886163135L, 3190187286L, 10150595910L, 28760021745L, 73006209045L, 166871334960L, 344867425584L, 646626422970L, 1103068603890L, 1715884494940L, 2438362177020L, 3169870830126L, 3773655750150L, 4116715363800L, 4116715363800L},
/* 46 */ {1L, 46L, 1035L, 15180L, 163185L, 1370754L, 9366819L, 53524680L, 260932815L, 1101716330L, 4076350421L, 13340783196L, 38910617655L, 101766230790L, 239877544005L, 511738760544L, 991493848554L, 1749695026860L, 2818953098830L, 4154246671960L, 5608233007146L, 6943526580276L, 7890371113950L, 8233430727600L},
/* 47 */ {1L, 47L, 1081L, 16215L, 178365L, 1533939L, 10737573L, 62891499L, 314457495L, 1362649145L, 5178066751L, 17417133617L, 52251400851L, 140676848445L, 341643774795L, 751616304549L, 1503232609098L, 2741188875414L, 4568648125690L, 6973199770790L, 9762479679106L, 12551759587422L, 14833897694226L, 16123801841550L, 16123801841550L},
/* 48 */ {1L, 48L, 1128L, 17296L, 194580L, 1712304L, 12271512L, 73629072L, 377348994L, 1677106640L, 6540715896L, 22595200368L, 69668534468L, 192928249296L, 482320623240L, 1093260079344L, 2254848913647L, 4244421484512L, 7309837001104L, 11541847896480L, 16735679449896L, 22314239266528L, 27385657281648L, 30957699535776L, 32247603683100L},
/* 49 */ {1L, 49L, 1176L, 18424L, 211876L, 1906884L, 13983816L, 85900584L, 450978066L, 2054455634L, 8217822536L, 29135916264L, 92263734836L, 262596783764L, 675248872536L, 1575580702584L, 3348108992991L, 6499270398159L, 11554258485616L, 18851684897584L, 28277527346376L, 39049918716424L, 49699896548176L, 58343356817424L, 63205303218876L, 63205303218876L},
/* 50 */ {1L, 50L, 1225L, 19600L, 230300L, 2118760L, 15890700L, 99884400L, 536878650L, 2505433700L, 10272278170L, 37353738800L, 121399651100L, 354860518600L, 937845656300L, 2250829575120L, 4923689695575L, 9847379391150L, 18053528883775L, 30405943383200L, 47129212243960L, 67327446062800L, 88749815264600L, 108043253365600L, 121548660036300L, 126410606437752L},
/* 51 */ {1L, 51L, 1275L, 20825L, 249900L, 2349060L, 18009460L, 115775100L, 636763050L, 3042312350L, 12777711870L, 47626016970L, 158753389900L, 476260169700L, 1292706174900L, 3188675231420L, 7174519270695L, 14771069086725L, 27900908274925L, 48459472266975L, 77535155627160L, 114456658306760L, 156077261327400L, 196793068630200L, 229591913401900L, 247959266474052L, 247959266474052L},
/* 52 */ {1L, 52L, 1326L, 22100L, 270725L, 2598960L, 20358520L, 133784560L, 752538150L, 3679075400L, 15820024220L, 60403728840L, 206379406870L, 635013559600L, 1768966344600L, 4481381406320L, 10363194502115L, 21945588357420L, 42671977361650L, 76360380541900L, 125994627894135L, 191991813933920L, 270533919634160L, 352870329957600L, 426384982032100L, 477551179875952L, 495918532948104L},
/* 53 */ {1L, 53L, 1378L, 23426L, 292825L, 2869685L, 22957480L, 154143080L, 886322710L, 4431613550L, 19499099620L, 76223753060L, 266783135710L, 841392966470L, 2403979904200L, 6250347750920L, 14844575908435L, 32308782859535L, 64617565719070L, 119032357903550L, 202355008436035L, 317986441828055L, 462525733568080L, 623404249591760L, 779255311989700L, 903936161908052L, 973469712824056L, 973469712824056L},
/* 54 */ {1L, 54L, 1431L, 24804L, 316251L, 3162510L, 25827165L, 177100560L, 1040465790L, 5317936260L, 23930713170L, 95722852680L, 343006888770L, 1108176102180L, 3245372870670L, 8654327655120L, 21094923659355L, 47153358767970L, 96926348578605L, 183649923622620L, 321387366339585L, 520341450264090L, 780512175396135L, 1085929983159840L, 1402659561581460L, 1683191473897752L, 1877405874732108L, 1946939425648112L},
/* 55 */ {1L, 55L, 1485L, 26235L, 341055L, 3478761L, 28989675L, 202927725L, 1217566350L, 6358402050L, 29248649430L, 119653565850L, 438729741450L, 1451182990950L, 4353548972850L, 11899700525790L, 29749251314475L, 68248282427325L, 144079707346575L, 280576272201225L, 505037289962205L, 841728816603675L, 1300853625660225L, 1866442158555975L, 2488589544741300L, 3085851035479212L, 3560597348629860L, 3824345300380220L, 3824345300380220L},
/* 56 */ {1L, 56L, 1540L, 27720L, 367290L, 3819816L, 32468436L, 231917400L, 1420494075L, 7575968400L, 35607051480L, 148902215280L, 558383307300L, 1889912732400L, 5804731963800L, 16253249498640L, 41648951840265L, 97997533741800L, 212327989773900L, 424655979547800L, 785613562163430L, 1346766106565880L, 2142582442263900L, 3167295784216200L, 4355031703297275L, 5574440580220512L, 6646448384109072L, 7384942649010080L, 7648690600760440L},
/* 57 */ {1L, 57L, 1596L, 29260L, 395010L, 4187106L, 36288252L, 264385836L, 1652411475L, 8996462475L, 43183019880L, 184509266760L, 707285522580L, 2448296039700L, 7694644696200L, 22057981462440L, 57902201338905L, 139646485582065L, 310325523515700L, 636983969321700L, 1210269541711230L, 2132379668729310L, 3489348548829780L, 5309878226480100L, 7522327487513475L, 9929472283517787L, 12220888964329584L, 14031391033119152L, 15033633249770520L, 15033633249770520L},
/* 58 */ {1L, 58L, 1653L, 30856L, 424270L, 4582116L, 40475358L, 300674088L, 1916797311L, 10648873950L, 52179482355L, 227692286640L, 891794789340L, 3155581562280L, 10142940735900L, 29752626158640L, 79960182801345L, 197548686920970L, 449972009097765L, 947309492837400L, 1847253511032930L, 3342649210440540L, 5621728217559090L, 8799226775309880L, 12832205713993575L, 17451799771031262L, 22150361247847371L, 26252279997448736L, 29065024282889672L, 30067266499541040L},
/* 59 */ {1L, 59L, 1711L, 32509L, 455126L, 5006386L, 45057474L, 341149446L, 2217471399L, 12565671261L, 62828356305L, 279871768995L, 1119487075980L, 4047376351620L, 13298522298180L, 39895566894540L, 109712808959985L, 277508869722315L, 647520696018735L, 1397281501935165L, 2794563003870330L, 5189902721473470L, 8964377427999630L, 14420954992868970L, 21631432489303455L, 30284005485024837L, 39602161018878633L, 48402641245296107L, 55317304280338408L, 59132290782430712L, 59132290782430712L},
/* 60 */ {1L, 60L, 1770L, 34220L, 487635L, 5461512L, 50063860L, 386206920L, 2558620845L, 14783142660L, 75394027566L, 342700125300L, 1399358844975L, 5166863427600L, 17345898649800L, 53194089192720L, 149608375854525L, 387221678682300L, 925029565741050L, 2044802197953900L, 4191844505805495L, 7984465725343800L, 14154280149473100L, 23385332420868600L, 36052387482172425L, 51915437974328292L, 69886166503903470L, 88004802264174740L, 103719945525634515L, 114449595062769120L, 118264581564861424L},
/* 61 */ {1L, 61L, 1830L, 35990L, 521855L, 5949147L, 55525372L, 436270780L, 2944827765L, 17341763505L, 90177170226L, 418094152866L, 1742058970275L, 6566222272575L, 22512762077400L, 70539987842520L, 202802465047245L, 536830054536825L, 1312251244423350L, 2969831763694950L, 6236646703759395L, 12176310231149295L, 22138745874816900L, 37539612570341700L, 59437719903041025L, 87967825456500717L, 121801604478231762L, 157890968768078210L, 191724747789809255L, 218169540588403635L, 232714176627630544L, 232714176627630544L},
/* 62 */ {1L, 62L, 1891L, 37820L, 557845L, 6471002L, 61474519L, 491796152L, 3381098545L, 20286591270L, 107518933731L, 508271323092L, 2160153123141L, 8308281242850L, 29078984349975L, 93052749919920L, 273342452889765L, 739632519584070L, 1849081298960175L, 4282083008118300L, 9206478467454345L, 18412956934908690L, 34315056105966195L, 59678358445158600L, 96977332473382725L, 147405545359541742L, 209769429934732479L, 279692573246309972L, 349615716557887465L, 409894288378212890L, 450883717216034179L, 465428353255261088L},
/* 63 */ {1L, 63L, 1953L, 39711L, 595665L, 7028847L, 67945521L, 553270671L, 3872894697L, 23667689815L, 127805525001L, 615790256823L, 2668424446233L, 10468434365991L, 37387265592825L, 122131734269895L, 366395202809685L, 1012974972473835L, 2588713818544245L, 6131164307078475L, 13488561475572645L, 27619435402363035L, 52728013040874885L, 93993414551124795L, 156655690918541325L, 244382877832924467L, 357174975294274221L, 489462003181042451L, 629308289804197437L, 759510004936100355L, 860778005594247069L, 916312070471295267L, 916312070471295267L},
/* 64 */ {1L, 64L, 2016L, 41664L, 635376L, 7624512L, 74974368L, 621216192L, 4426165368L, 27540584512L, 151473214816L, 743595781824L, 3284214703056L, 13136858812224L, 47855699958816L, 159518999862720L, 488526937079580L, 1379370175283520L, 3601688791018080L, 8719878125622720L, 19619725782651120L, 41107996877935680L, 80347448443237920L, 146721427591999680L, 250649105469666120L, 401038568751465792L, 601557853127198688L, 846636978475316672L, 1118770292985239888L, 1388818294740297792L, 1620288010530347424L, 1777090076065542336L, 1832624140942590534L}
};
}
