Fast midpoint between two integers without overflow

2 years ago

source link: https://lemire.me/blog/2022/12/06/fast-midpoint-between-two-integers-without-overflow/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Fast midpoint between two integers without overflow

Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth.

Thus we sometimes need a fast algorithm to find the midpoint in an interval of integers.The following simple routine to find the midpoint is incorrect:

int f(int x, int y) {
  return (x + y)/2;
}

If the integers use a 64-bit two’s complement representation, we could pick 1 for x and 9223372036854775807 for y, and then the result of the function could be a large negative value.

Efficient solutions are provided by Warren in Hacker’s Delight (section 2.5):

int f(int x, int y) { 
  return (x|y) - ((x^y)>>1); 
}

int f(int x, int y) { 
  return ((x^y)>>1) + (x&y); 
}

They provide respectively the smallest value no smaller than (x+y)/2 and the largest value no larger than (x+y)/2. The difference between the two values is (x ^ y) & 1 (credit: Harold Aptroot).

They follow from the following identities: x+y=(x^y)+2*(x&y) and x+y=2*(x|y)-(x^y).

Update: Reader BartekF observes that C++20 added a dedicated function for this problem: std::midpoint.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire

Recommend

devblogs.microsoft.com 3 years ago
Cache

On finding the average of two unsigned integers without overflow

On finding the average of two unsigned integers without overflow Raymond February 7th, 2022

Github github.com 3 years ago
Cache

Support 128-bit integers on platforms without native support by antoyo · Pull Re...

New issue Support 128-bit integers on platforms without native support #103

arpitbhayani.me 3 years ago
Cache

Midpoint Insertion Strategy in MySQL LRU Cache

Midpoint Insertion Strategy in MySQL LRU Cache 8 min read 455 reads Published on 26...

www.geeksforgeeks.org 3 years ago
Cache

Midpoint circle drawing algorithm

Midpoint circle drawing algorithmVideo Player is loading.Loaded: 0%Remaining Time -0:00Midpoint circle drawing algorithm420...

thispointer.com 2 years ago
Cache

Generate Random Integers between 0 and 9 in Python

In this Python tutorial, we will learn how to generate random integers between 0 and 9 in Python? Table Of Contents Let’s dive into the tutorial. Generate r...