HAKMEM Item 175



HAKMEM Item 175 describes a concise algorithm that, given an integer, calculates the next higher integer with the same number of one bits.
function hakmemItem175(value){

  // find the lowest one bit in the input
  var lowestBit = value & -value;

  // determine the leftmost bits of the output
  var leftBits = value + lowestBit;

  // determine the difference between the input and leftmost output bits
  var changedBits = value ^ leftBits;

  // determine the rightmost bits of the output
  var rightBits = (changedBits / lowestBit) >>> 2;

  // return the complete output
  return (leftBits | rightBits);
}
it determines the leftmost and rightmost bits of the output separately and then combines them. It starts by performing a logical ‘and’ of the input and its negative. 
By adding this on to the original input, we obtain the leftmost bits of the output:
Next it performs a logical ‘xor or’ of the input and this value to determine which bits have changed:
To produce the rightmost bits of the output, it then divides this value by the lowest one bit (in order to remove any trailing zero bits) and then logically shifts the new value two bits to the right (to remove the extra one bits that resulted from the bit that moved):
Finally, it performs a logical ‘or’ on the leftmost and rightmost output bits to combine them into the answer:
Read full article from HAKMEM Item 175

No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts