Bitwise and in place of modulus operator

by

First of all, it’s actually not accurate to say that

x % 2 == x & 1

Simple counterexample: x = -1. In many languages, including Java, -1 % 2 == -1. That is, % is not necessarily the traditional mathematical definition of modulo. Java calls it the “remainder operator”, for example.

With regards to bitwise optimization, only modulo powers of two can “easily” be done in bitwise arithmetics. Generally speaking, only modulo powers of base b can “easily” be done with base b representation of numbers.

In base 10, for example, for non-negative N, N mod 10^k is just taking the least significant k digits.

References

More Related Contents:

  1. Complexity of absolute difference and sum
  2. Custom Weighted Scale [closed]
  3. What is tail recursion?
  4. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  5. Getting the closest string match
  6. How do I search for a number in a 2d array sorted left to right and top to bottom?
  7. How to compute Discrete Fourier Transform?
  8. Difference between Big-O and Little-O Notation
  9. How does finding a cycle start node in a cycle linked list work?
  10. Quicksort: Choosing the pivot
  11. Breadth First Vs Depth First
  12. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  13. Efficient list intersection algorithm
  14. Rounding to an arbitrary number of significant digits
  15. Time complexity of Euclid’s Algorithm
  16. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  17. What would cause an algorithm to have O(log log n) complexity?
  18. What is pseudopolynomial time? How does it differ from polynomial time?
  19. Quick sort Worst case
  20. Is there an algorithm for color mixing that works like mixing real colors?
  21. How can I calculate the age of a person in year, month, days?
  22. Performing Breadth First Search recursively
  23. Quicksort: Iterative or Recursive
  24. How best to sum up lots of floating point numbers?
  25. Polygon enclosing a set of points
  26. Find the index of a given permutation in the sorted list of the permutations of a given string
  27. Algorithm to list unique permutations of string with duplicate letters
  28. Algorithm to mix sound
  29. Collision detection of huge number of circles
  30. finding a^b^c^… mod m

Leave a Comment