Changing one given bit in a binary address in C

Question

I'm working on the "buddy-allocation" for a memory management project in C (see page 14 of this .pdf).

I'd like to find the "buddy" of a given address, knowing that the two buddies are only one-bit-different (the size of the chunk tells us which bit changes). For example, if one of the two 32-bits buddy chunks has the binary address 0b110010100, the second one will be located at 0b110110100 (the 6th bit from the right changes, as 32=2^(6-1)).

I'd like to implement that in C, without exponentiation algorithms because I'm trying to make my program as fast-executing as possible. At best I'd use a tool to manipulate bits, if that exists. Any hints?

EDIT: the type of the addresses is void*. With the solutions posted below, gcc won't let me compile.

EDIT2: I've tried the answers posted below with the XOR operator, but I can't compile because of the type of the addresses. Here's what I've tried :

void* ptr1 = mmap(NULL, 640000, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_FILE | MAP_PRIVATE, -1, 0);
    printf("%p\n", ptr1);
    void* ptr2 = ptr1+0x15f6d44;
    printf("%p\n", ptr2);
    void* ptr3 = (void*)(ptr2-ptr1);
    printf("%p\n", ptr3);
    void* ptr4 = ptr3 ^ (1 << 6);
    printf("%p\n", ptr4);

and the gcc error :

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

See http://stackoverflow.com/questions/1746613/bitwise-operation-and-usage/1746642#1746642 — paxdiablo, Sep 30 '15 at 07:44
See http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c-c — light_keeper, Sep 30 '15 at 07:48

sansuiso · Accepted Answer · 2015-10-02T07:26:05.493

4

It looks like you just want to toggle a given bit, which is achieved using an XOR operation:

buddy_adr = (unsigned long)adr ^ (1 << bit_location);

The cast to unsigned long is required to avoid errors of undefined XOR operation on type void*.

Depending on your compiler settings, you may also get a warning about creating a pointer (i.e., an address) by casting an integer, which is obviously dangerous in the general case (you could pass an invalid address value). To silent this warning, cast back the result to void* to let the compiler know that you know what you are doing:

buddy_adr = (void *)((unsigned long(adr ^ (1 << bit_location));

Note that in embedded system programming (where I've used this technique most of the time since many peripherals are memory-mapped) you would usually "simplify" this line of code using macros like TOGGLE_BIT(addr, bit) and INT_TO_ADDR(addr).

edited Oct 02 '15 at 07:26

answered Sep 30 '15 at 07:46

sansuiso

9,259
1
40
58

This is almost what I looked for, but my address has void* for a type. And gcc won't let me compile this way. Do you know how to proceed ? – AdrienW Oct 01 '15 at 13:55
Just cast your address to unsigned int, this should be enough for the compiler, – sansuiso Oct 01 '15 at 14:29
I don't really understand. I've tried the following : `void* ptr1 = mmap(NULL, 640000, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_FILE | MAP_PRIVATE, -1, 0); printf("%p\n", ptr1); void* ptr2 = ptr1+0x15f6d44; printf("%p\n", ptr2); void* ptr3 = (void*)(ptr2-ptr1); printf("%p\n", ptr3); void* ptr4 = ptr3 ^ (1 << 6); printf("%p\n", ptr4);` And I'm getting this error : `error: invalid operands to binary ^ (have ‘void *’ and ‘int’)` What should I change ? – AdrienW Oct 01 '15 at 15:17
Please have a look at the updated answer. In a nutshell, you have to transform your void type to (unsigned) int, apply arithmetic operations on the int, then take the result back to the void* world. – sansuiso Oct 02 '15 at 07:27
This is amazing ! The double cast works perfectly, thanks so much – AdrienW Oct 03 '15 at 10:16

score 3 · Answer 2 · answered Sep 30 '15 at 07:45

3

You can set one bit with a | bitwise or.

adr = adr | 0x10;

answered Sep 30 '15 at 07:45

weston

54,145
21
145
203

unwind · Answer 3 · 2015-10-01T13:56:43.690

3

A tool? To manipulate bits? You don't need a "tool", that's about as primitive an operation as you can do.

uint32_t address = 0x0194;

address |= 1 << 5; /* This sets the sixth bit. */

If you really want to toggle the bit, i.e. set if if it's clear, but clear it if it's set, you use the bitwise XOR operator:

address ^= 1 << 5;

This is not "exponentiation", it's just a bitwise XOR.

If the address is held in a pointer register, either cast or copy to integer (uintptr_t) and the copy back.

edited Oct 01 '15 at 13:56

answered Sep 30 '15 at 07:45

unwind

391,730
64
469
606

This is almost what I looked for, but my address has void* for a type. And gcc won't let me compile this way. Do you know how to proceed ? – AdrienW Oct 01 '15 at 13:55

score 2 · Answer 4 · answered Sep 30 '15 at 07:47

This is case of bit manipulation which is very common in c programming if you want to change xxbxxxxx simply XOR this with xx1xxxxx. XOR topple the given bit. If you want to make it 1 just use OR (|) with all bits 0 except that bit 1 which you want to turn on

score 1 · Answer 5 · answered Sep 30 '15 at 08:32

1

a more compact way to do this

#define BIT_ON(x,bit)           (x |= ( 1 << (bit-1)) )
#define BIT_TOGGLE(x,bit)       (x ^= ( 1 << (bit-1)) )
#define BIT_OFF(x,bit)          (x &= ~( 1 << (bit-1)) )

answered Sep 30 '15 at 08:32

asio_guy

3,667
2
19
35

Changing one given bit in a binary address in C

5 Answers5