How to determine if two pointers point to the same block of memory

Question

I am trying to solve the following problem:

/*
 * Return 1 if ptr1 and ptr2 are within the *same* 64-byte aligned
 * block (or word) of memory. Return zero otherwise.
 *
 * Operators / and % and loops are NOT allowed.
 */
/*

I have the following code:

int withinSameBlock(int * ptr1, int * ptr2) {
  // TODO
  int temp = (1 << 31) >> 25;
  int a = ptr1;
  int b = ptr2;
  return (a & temp) == (b & temp);
}

I have been told that this correctly solves the problem, but I am unsure how it works. Specifically, how does the line int temp = (1 << 31) >> 25; help to solve the problem?

Answer 1

The line:

int temp = (1 << 31) >> 25;

is either incorrect or triggers undefined behavior (depending on wordsize). It just so happens that the undefined behavior on your machine and your compiler does the right thing and just happens to give the correct answer. To avoid undefined behavior and make the code clearer, you should use:

int withinSameBlock(int * ptr1, int * ptr2) {
    uintptr_t temp = ~(uintptr_t)63;
    uintptr_t a = (uintptr_t)ptr1;
    uintptr_t b = (uintptr_t)ptr2;
    return (a & temp) == (b & temp);
}

Answer 2

I'm not sure where you get that code (homework?) but this is terrible. 1. casting pointer to int and do arithmetics is generally very bad practice. The actual size is undefined by those primitive types, for instant, it breaks on every architecture that pointer or int is not 32-bit.

You should use uintptr_t, which is generally larger than or equal to the size of a pointer (except for theoretical arch permitted by ambigous spec)

For example:

#include <stdint.h>
#include <stdio.h>

int withinSameBlock(int * ptr1, int * ptr2) {
  uintptr_t p1 = reinterpret_cast<uintptr_t>(ptr1);
  uintptr_t p2 = reinterpret_cast<uintptr_t>(ptr2);
  uintptr_t mask = ~ (uintptr_t)0x3F;
  return (p1 & mask) == (p2 & mask);
}


int main() {
  int* a = (int*) 0xdeadbeef;
  int* b = (int*) 0xdeadbeee;
  int* c = (int*) 0xdeadc0de;
  printf ("%p, %p: %d\n", a, b, withinSameBlock(a, b));
  printf ("%p, %p: %d\n", a, c, withinSameBlock(a, c));
  return 0;
}

Answer 3

First, we need to be clear that the code will only work on systems where a pointer is 32 bits, and int is also 32 bits. On a 64-bit system, the code will fail miserably.

The left shift (1 << 31) sets the most significant bit of the int. In other words, the line

int temp = (1 << 31);

is the same as

int temp = 0x80000000;

Since an int is a signed number, the most significant bit is the sign bit. Shifting as signed number to the right copies the sign bit into lower order bits. So shifting to the right 25 times results in a value that has a 1 in the upper 26 bits. In other words, the line

int temp = (1 << 31) >> 25;

is the same as (and would be much clearer if it was written as)

int temp = 0xffffffc0;

The line

return (a & temp) == (b & temp);

compares the upper 26 bits of a and b, ignoring the lower 6 bits. If the upper bits match, then a and b point to the same block of memory.

Answer 4

Assuming 32 bit pointers, if the two pointers are in the same 64-byte block of memory, then their addresses will vary only in the 6 least significant bits.

(1 << 31) >> 25 will give you a bitmask that looks like this:

11111111111111111111111111000000

a=ptr1 and b=ptr2 will set a and b equal to the value of the pointers, which are memory addresses. The bitwise AND of temp with each of these (i.e., a&temp and b&temp) will mask off the last 6 bits of the addresses held by a and b. If the remaining 26 bits are the same, then the original addresses must have been within 64 bytes of each other.

Demo code:

#include <stdio.h>

void main()
{
    int temp = (1 << 31) >> 25;
    printf("temp=%x\n",temp);
    int p=5, q=6;
    int *ptr1=&p, *ptr2=&q;
    printf("*ptr1=%x, *ptr2=%x\n",ptr1, ptr2);
    int a = ptr1;
    int b = ptr2;
    printf("a=%x, b=%x\n",a,b);
    if ((a & temp) == (b & temp)) printf("true\n");
    else printf("false\n");
}