1.  /* Lowest Common Ancestor using GiM's lca-trick in full binary tree test 1
2.   *
3.   * Michal 'GiM' Spadlinski http://gim.org.pl/ gim@@at@@skrzynka@@dot@@pl
4.   *
5.   * compile:
6.   * gcc -o test_lca{,.c} bsfr.c
7.   *
8.   * to print output in binary instead of hex values, put anything
9.   * on command line, after programs name.
10.   *
11.   * redistribute under the terms of GPL
12.   */
13.  #include <stdio.h>
14.  #include <math.h>
15.  #include "bsfr.h"
16.  
17.  #define BITS 4
18.  
19.  int SIZE = 0;
20.  
21.  const int use_ansi = 1;
22.  
23.  void binary(unsigned int ch, int size)
24.  {
25.   unsigned int i;
26.   if (size)
27.   {
28.   for (i = 1 << (size - 1); i > 0; i >>= 1)
29.   fputc ('0' + !! (ch & i), stdout);
30.   } else {
31.   printf ("%02x", ch);
32.   }
33.  }
34.  
35.  /* very fast lowest common ancestor
36.   * in binary inorder tree
37.   */
38.  int lca_bin (int a, int b)
39.  {
40.   if (a == b)
41.   return a;
42.  
43.   if (b > a)
44.   a ^= b ^= a ^= b;
45.  
46.   /* GiM's lca-trick
47.   * if smaller number is even, and bigger is in _specified_ range,
48.   * return lower one :)
49.   */
50.   if (!(b & 1) && a < b + (1 << (bsf (b))))
51.   return (b);
52.  
53.   return a & ~((1 << bsr (a ^ b))-1);
54.  }
55.  
56.  int main(int argc, char **argv)
57.  {
58.   int j, i;
59.  
60.   if (argc > 1)
61.   SIZE = BITS;
62.  
63.   for (j = 0; j < 1 << BITS; j++)
64.   {
65.   for (i = 0; i < 1 << BITS; i++)
66.   {
67.   if (!j)
68.   binary (i, SIZE), printf (" %s",i?"":" ");
69.   else {
70.   if (i == 0)
71.   binary (j, SIZE), printf (" | ");
72.   else {
73.   if (use_ansi && i == j) printf("\033[1m");
74.   binary ( lca_bin(i, j) , SIZE);
75.   if (use_ansi && i == j) printf("\033[0m");
76.   printf (" ");
77.   }
78.   }
79.   }
80.   printf("\n");
81.   }
82.  
83.   return 0;
84.  }
85.  

This document should validate, please check by clicking: