在C中使用带有指针的XOR

Question

上周,我们的老师给了我们一个在C中制作双链表的任务,而不使用结构中的两个指针; 我们必须使用一个指针指向列表中的下一个和上一个节点来实现它.我确信这样做的唯一方法是使用XOR合并下一个和上一个方向,然后指向"混合"内存分配,如果我需要prev或next的方向,我可以再次使用XOR得到我需要的一个内存值.

我设计了算法,我认为它会起作用,但当我尝试实现解决方案时,我遇到了一个问题.当我尝试编译程序时,编译器告诉我,我不能使用XOR(^)指针:

invalid operands to binary ^ (have ‘void *’ and ‘node *’)

以下是在列表前面添加节点的功能:

typedef  struct node_list{
  int data;
  struct node_list *px;
}  node;

node* addfront ( node *root, int data ){ 
  node *new_node, *next;

  new_node = malloc ( sizeof ( node )); 
  new_node -> data = data;

  new_node -> px = (NULL ^ root);//this will be the new head of the list

  if ( root != NULL ){           // if the list isn't empty
    next = ( NULL ^ root -> px );  // "next" will be the following node of root, NULL^(NULL^next_element).
    root = ( new_node ^ next );    //now root isn't the head node, so it doesn't need to point null.
  }
}

我在C++中读到,指针的XOR是有效的.有关如何在C中实现此功能的任何想法？我也读过我需要使用的地方intptr_t,但我不明白该怎么做.

Answer 1

#include <stdint.h>

(void *)((uintptr_t)p1 ^ (uintptr_t)p2)

从技术上讲,C并没有强制void *要求能够存储任何价值uintptr_t; 因为值(uintptr_t)p1 ^ (uintptr_t)p2(让我们调用它X)实际上并不是uintptr_t有效指针的转换,实现定义的(void *)X返回转换uintptr_t可能不会产生值X,从而破坏了你想要做的一切.

幸运的是,这很容易通过使用类型的对象uintptr_t而不是void *存储"xor指针"来解决.简单地说:

uintptr_t xor_ptr = (uintptr_t)p1 ^ (uintptr_t)p2;

然后您可以通过以下方式安全地p1从p2(或反之亦然)恢复:

(void *)(xor_ptr ^ (uintptr_t)p2)

由于该值 xor_ptr ^ (uintptr_t)p2等于(uintptr_t)p1,C的转义定义uintptr_t保证该值void *(作为指针)等于p1(根据C11 7.20.1.4).