使用XOR实现双链表,每个节点有一个指针

Question

我遇到了XOR双链接列表的问题,该列表有一个必须包含节点的NEXT和PREV指针的指针.我必须xor地址指针这样做,但我不能.我可以分配一个与两个地址进行异或的内存地址但是我无法获得其地址的值(这有分段错误错误):

int main(){
    int* ptr = new int;
    int *ptr2 = new int;
    ptr2 = (int*)((unsigned long)ptr ^ (unsigned long)ptr2);
    *ptr2= 5;        /here has segmentation fault
    cout <<*ptr2;    
    return 0;

为什么这段代码有错误？我该如何解决？

---

感谢您的回复,但我无法转移我的想法,换句话说我说我的问题:通常我们有一个指针,通过" new "(用c ++)关键字为它分配内存空间.我们的指针保留的这个地址是由os确定的,对吗？例如,指针指向它的地址是0x8f3400b(这是可以保留的内存空闲的地方)我想通过不使用像这样的代码的新关键字来手动执行此操作:

int* ptr1 = (int*) 0x2355;
int* ptr2 = (int*) 0x23ff;

现在我不知道地址0x2355和0x23ff是否可以保留？然后我决定" 新 "这些指针,然后对它们进行异或,如下所示:

int* ptr1 = new int     //ptr1 is now manage by OS
int* ptr2 = new int     //like ptr1 ...

然后我想要对这些指针进行异或,并建立一个新的空间来附加一个节点,这是第三个节点,但我不能解决它是正确的但是当我想评估它时发生了分段错误:

int* ptr1 = new int;    // for example the address is X
int* ptr2 = new int;    // for example the address is Y
int* ptr3 = (int*)((unsigned long)ptr1 ^ (unsigned long)ptr2);    //the final address is X^Y

我怎么能纠正这个？我不知道如何使用intptr_t和其他请帮助我谢谢

Answer 1

有一个非常难看的技巧(如果它有效)让你实现一个双链表,每个节点只有一个指针.如你所说,它需要xor'ing指针值.

这篇维基百科文章讨论了它.

这几乎总是一个非常糟糕的主意.该语言并不能保证它完全可以工作.

如果你必须这样做,那么将指针值转换为uintptr_t或intptr_t(这些类型甚至不保证存在,但它们可能会存在),在<stdint.h>或中声明<cstdint>.

xor'ing两个指针值的结果将不是一个有效的指针,并且任何使用它作为一个的尝试都会在你的脸上爆炸(如果你很幸运).从这样的操作中获取有效指针的唯一方法是反转它,获取原始指针值.你*ptr2 = 5;导致分段错误就不足为奇了.

如果你正在做这个练习,只是为了看看你是否可以让它工作,一定要继续前进并享受乐趣.

如果您认为对此有一些实际要求,则不会.如果你想要一个双向链表,每个节点只有两个指针.或者,更好的是,由于您使用C++编程,因此请使用标准库容器类之一.