Bit Twiddling with LeetCode Problem #1342

The Problem

The Naive Solution

  • 7 is odd, subtract 1
  • 6 is even, divide by 2
  • 3 is odd, subtract 1
  • 2 is even, divide by 2
  • 1 is odd, subtract 1
  • 0 is 0, we are done.

Wasted Iterations

  • Whenever we divide an even number by 2, the result may be even or odd.
  • Whenever we subtract 1 from an odd number, the result will always be even.
  • subtract 1, add 1 step to the counter
  • divide by 2, add 1 step to the counter
  • subtract 1 and divide by 2, add 2 steps to the counter

Binary Preface

The Binary Shift

  • 193 * 10 = 1930
  • 11000001 << 1 = 110000010 = 386 base 10
  • 193 / 10 = 19
  • 11000001 >> 1 = 1100000 = 96 base 10
  • 193 << 4 = 3088 [effectively 193 * 2 * 2 * 2 * 2]
  • 193 >> 4 = 12 [effectively 193 / 2 / 2 / 2 / 2]

The Optimized Solution

Hamming Epilogue

  • 11000001 [ODD] >> 1 = 1100000
  • 1100000 >> 1 = 110000
  • 110000 >> 1 = 11000
  • 11000 >> 1 = 1100
  • 1100 >> 1 =110
  • 110 >> 1 = 11
  • 11 [ODD] >> 1 = 1
  • 1 [ODD] >> 1 = 0

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Bryan Haney

Bryan Haney

Full stack web developer with a passion for number theory and algorithms.