在C语言中使用异或运算符来处理指针

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，但我不知道该怎么做。

- angel208

---

可能是如何理解XOR链表的工作原理？的重复问题。 - Afforess

@Afforess 我认为原帖作者知道算法的工作原理，只是不知道具体的C语言结构来实现它。 - Fred Foo

“.”和“->”运算符的优先级非常高；在它们周围留出空格是不常见的。请始终使用root->px等方式。 - Jonathan Leffler

对于谷歌员工，语句myType * ptr = (myType *)(((void *)a) ^ ((void *)b));会导致VS 2017编译器出错，显示为error C2296: '^': illegal, left operand has type 'void *'和error C2297: '^': illegal, right operand has type 'void *'。 - JamesThomasMoon

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 *来存储您的“异或指针”来轻松解决。只需执行以下操作：

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

然后，您可以通过以下方式安全地从p2（或反过来）恢复p1：

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

由于值xor_ptr ^ (uintptr_t)p2等于(uintptr_t)p1，C语言中uintptr_t的定义保证该值转换为void *后与p1相等（作为指针）(参考C11 7.20.1.4)。

- R.. GitHub STOP HELPING ICE

---

uintptr_t是一个整数类型（其中定义了^，并且不违反约束），能够表示任何指针。因此，将其转换为uintptr_t，在那里进行算术运算，然后再转换回指针即可解决您的问题。 - R.. GitHub STOP HELPING ICE

@2501：异或操作不是未定义行为。将结果转换回void *类型是实现定义的，因此存在一个问题，即void *可能无法准确地表示值((uintptr_t)p1 ^ (uintptr_t)p2)（以一种可以从p1或p2中恢复原始值的方式），这在我的答案中是一种技术缺陷。但是，可以通过将“异或指针”存储为uintptr_t而不是void *来解决这个问题，并且只有在执行第二次异或以获取原始值后才将其转换回void *。 - R.. GitHub STOP HELPING ICE

通过 "xor is ub"，我指的是答案中提到的整个操作。这在评论开头已经暗示了。（显然，unsigned integers上的xor是已定义的。）将void指针存储为uintptr_t似乎是一个聪明的解决方案，但它并没有解决问题。即使uintptr_t被修改，转换回void的定义也不会成立，即使它具有相同的值。 - 2501

我承认行为实际上是实现定义的，因为我在推理中忘记包括6.3.2.3 p5。所以你是正确的。也许考虑将此包含在相当枯燥的答案中。 - 2501

@2501：如果它们具有相同的值，则转换回来肯定是被定义的。C 定义了值的转换而不是对象的转换。同样的值被转换两次会产生相同的结果。对于无符号的 x（因此我们不必担心溢出），(T)(x+1-1) 总是与 (T)x 相同。异或运算等同适用。 - R.. GitHub STOP HELPING ICE

Answer 2

你可以使用reinterpret_cast对指针执行XOR操作。请注意，虽然它能够工作，但不建议这样做。

#include<iostream>
using namespace std;

int main()
{
    int* x = new int(1);
    int* y = new int(2);

    cout << *x << ", " << *y << endl; // outputs 1, 2

    int addr1 = reinterpret_cast<int>(x);
    int addr2 = reinterpret_cast<int>(y);
    int addr3 = (addr1 ^ addr2); // xor on both pointers

    int* ptr = reinterpret_cast<int*>(addr3 ^ addr2); // xor "away" *y, ptr points on x now
    *ptr = 5;
    cout << *x << endl; // 5

    ptr = reinterpret_cast<int*>(addr3 ^ addr1); // xor "away" *x, ptr points on y now
    *ptr = 6;
    cout << *y << endl; // 6

    delete x;
    delete y;
    return 0;
}

- Andrushenko Alexander

Answer 3

这里我举例说明了如何使用双向异或链表，这是一种具有节点的列表，每个节点都存储在单个int变量中指向前一个和后一个节点的指针： 我在这里明确使用裸指针，以更好地演示访问机制。

#include<cassert>

using namespace std;

struct ListNode
{
    int val;
    uint64_t both;
    ListNode(int v) : val(v), both(0) {}
};

struct XORList
{
    ListNode* head;
    ListNode* last;
    unsigned size;
    XORList() : head(nullptr), last(nullptr), size(0) {}

    void addNode(int x)
    {
        if (head == nullptr)
        {
            head = new ListNode(x);
            last = head;
        }
        else
        {
            ListNode* newNode = new ListNode(x);
            last->both = (last->both ^ (uint64_t ) newNode);
            uint64_t prev_node = (uint64_t) last;
            last = newNode;
            last->both = prev_node;
        }
        size++;
    }

    int get(unsigned idx)
    {
        if (idx >= size){
            throw("Out of bounds.");
        }

        ListNode* cur = head;
        unsigned i = 0;
        uint64_t prev_node = 0;
        while ((cur != nullptr) && (i < idx))
        {
            uint64_t nextNode = (prev_node ^ cur->both);
            prev_node = (uint64_t) cur;
            cur = (ListNode*) nextNode;
            i++;
        }
        return cur->val;
    }

    ~XORList()
    {
        ListNode* cur = head;
        uint64_t prev_node = 0;
        while (cur != nullptr)
        {
            uint64_t nextNode = (prev_node  ^ cur->both);
            prev_node  = (uint64_t) cur;
            delete cur;
            cur = (ListNode*) nextNode;
        }
    }
};

int main()
{
    XORList xorList;
    xorList.addNode(1);
    xorList.addNode(2);
    xorList.addNode(3);
    xorList.addNode(4);
    assert(xorList.get(0) == 1);
    assert(xorList.get(1) == 2);
    assert(xorList.get(2) == 3);
    assert(xorList.get(3) == 4);
}

- Andrushenko Alexander