What is the behaviour of this function? (Power of two)

I have next function:

static inline int nextPowerOfTwo(int n) {

    n--;



    n = n >>  1 | n;

    n = n >>  2 | n;

    n = n >>  4 | n;

    n = n >>  8 | n;

    n = n >> 16 | n;

    //  n = n >> 32 | n;    //  For 64-bit ints



    return ++n;

}

But I do not know which is his behavior (the function output -his functionality-)

I do not know neither what is the behavior of each line (n value after each line).

Can someone explain me it?

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

1

Your question is not clear. You can run the code and see what it does. Please post the output that you are seeing.
– John Murray
Nov 23 '18 at 23:14

add a comment |

I have next function:

static inline int nextPowerOfTwo(int n) {

    n--;



    n = n >>  1 | n;

    n = n >>  2 | n;

    n = n >>  4 | n;

    n = n >>  8 | n;

    n = n >> 16 | n;

    //  n = n >> 32 | n;    //  For 64-bit ints



    return ++n;

}

But I do not know which is his behavior (the function output -his functionality-)

I do not know neither what is the behavior of each line (n value after each line).

Can someone explain me it?

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

1

Your question is not clear. You can run the code and see what it does. Please post the output that you are seeing.
– John Murray
Nov 23 '18 at 23:14

add a comment |

I have next function:

static inline int nextPowerOfTwo(int n) {

    n--;



    n = n >>  1 | n;

    n = n >>  2 | n;

    n = n >>  4 | n;

    n = n >>  8 | n;

    n = n >> 16 | n;

    //  n = n >> 32 | n;    //  For 64-bit ints



    return ++n;

}

But I do not know which is his behavior (the function output -his functionality-)

I do not know neither what is the behavior of each line (n value after each line).

Can someone explain me it?

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

I have next function:

static inline int nextPowerOfTwo(int n) {

    n--;



    n = n >>  1 | n;

    n = n >>  2 | n;

    n = n >>  4 | n;

    n = n >>  8 | n;

    n = n >> 16 | n;

    //  n = n >> 32 | n;    //  For 64-bit ints



    return ++n;

}

But I do not know which is his behavior (the function output -his functionality-)

I do not know neither what is the behavior of each line (n value after each line).

Can someone explain me it?

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

edited Nov 26 '18 at 14:35

Stoogy

545522

edited Nov 26 '18 at 14:35

Stoogy

545522

edited Nov 26 '18 at 14:35

Stoogy

545522

asked Nov 23 '18 at 22:58

JuMoGar

7891217

asked Nov 23 '18 at 22:58

JuMoGar

7891217

asked Nov 23 '18 at 22:58

JuMoGar

7891217

1

Your question is not clear. You can run the code and see what it does. Please post the output that you are seeing.
– John Murray
Nov 23 '18 at 23:14

add a comment |

1

Your question is not clear. You can run the code and see what it does. Please post the output that you are seeing.
– John Murray
Nov 23 '18 at 23:14

Your question is not clear. You can run the code and see what it does. Please post the output that you are seeing.
– John Murray
Nov 23 '18 at 23:14

add a comment |

1 Answer
1

active

oldest

votes

That code comes from Bit Twiddling Hacks

Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v



v--;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

v++;
[...]

It works by copying the highest set bit to all of the lower
bits, and then adding one, which results in carries that set all of
the lower bits to 0 and one bit beyond the highest set bit to 1. If
the original number was a power of 2, then the decrement will reduce
it to one less, so that we round up to the same original value.

The obvious versions for 16, 32 and 64 bit:

#include <stdint.h>



uint16_t round_u16_to_pow2(uint16_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v++;

    return v;

}



uint32_t round_u32_to_pow2(uint32_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v++;

    return v;

}



uint64_t round_u64_to_pow2(uint64_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v |= v >> 32;

    v++;

    return v;

}

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

1

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

|
show 2 more comments

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53453693%2fwhat-is-the-behaviour-of-this-function-power-of-two%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

That code comes from Bit Twiddling Hacks

Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v



v--;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

v++;
[...]

It works by copying the highest set bit to all of the lower
bits, and then adding one, which results in carries that set all of
the lower bits to 0 and one bit beyond the highest set bit to 1. If
the original number was a power of 2, then the decrement will reduce
it to one less, so that we round up to the same original value.

The obvious versions for 16, 32 and 64 bit:

#include <stdint.h>



uint16_t round_u16_to_pow2(uint16_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v++;

    return v;

}



uint32_t round_u32_to_pow2(uint32_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v++;

    return v;

}



uint64_t round_u64_to_pow2(uint64_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v |= v >> 32;

    v++;

    return v;

}

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

1

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

|
show 2 more comments

That code comes from Bit Twiddling Hacks

Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v



v--;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

v++;
[...]

It works by copying the highest set bit to all of the lower
bits, and then adding one, which results in carries that set all of
the lower bits to 0 and one bit beyond the highest set bit to 1. If
the original number was a power of 2, then the decrement will reduce
it to one less, so that we round up to the same original value.

The obvious versions for 16, 32 and 64 bit:

#include <stdint.h>



uint16_t round_u16_to_pow2(uint16_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v++;

    return v;

}



uint32_t round_u32_to_pow2(uint32_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v++;

    return v;

}



uint64_t round_u64_to_pow2(uint64_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v |= v >> 32;

    v++;

    return v;

}

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

1

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

|
show 2 more comments

That code comes from Bit Twiddling Hacks

Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v



v--;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

v++;
[...]

It works by copying the highest set bit to all of the lower
bits, and then adding one, which results in carries that set all of
the lower bits to 0 and one bit beyond the highest set bit to 1. If
the original number was a power of 2, then the decrement will reduce
it to one less, so that we round up to the same original value.

The obvious versions for 16, 32 and 64 bit:

#include <stdint.h>



uint16_t round_u16_to_pow2(uint16_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v++;

    return v;

}



uint32_t round_u32_to_pow2(uint32_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v++;

    return v;

}



uint64_t round_u64_to_pow2(uint64_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v |= v >> 32;

    v++;

    return v;

}

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

That code comes from Bit Twiddling Hacks

Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v



v--;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

v++;
[...]

It works by copying the highest set bit to all of the lower
bits, and then adding one, which results in carries that set all of
the lower bits to 0 and one bit beyond the highest set bit to 1. If
the original number was a power of 2, then the decrement will reduce
it to one less, so that we round up to the same original value.

The obvious versions for 16, 32 and 64 bit:

#include <stdint.h>



uint16_t round_u16_to_pow2(uint16_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v++;

    return v;

}



uint32_t round_u32_to_pow2(uint32_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v++;

    return v;

}



uint64_t round_u64_to_pow2(uint64_t v)

{

    v--;

    v |= v >> 1;

    v |= v >> 2;

    v |= v >> 4;

    v |= v >> 8;

    v |= v >> 16;

    v |= v >> 32;

    v++;

    return v;

}

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

edited Nov 25 '18 at 18:57

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

answered Nov 23 '18 at 23:14

Swordfish

9,04211335

1

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

|
show 2 more comments

1

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

It does assume a 32-bit unsigned type so will have undefined behaviour for a 16-bit type and will not give the required result for (say) a 64-bit type.
– Peter
Nov 24 '18 at 0:35

@Peter Oh, And how could I contemplate 16-bit int ?
– JuMoGar
Nov 25 '18 at 18:22

And another question, if it is not so much trouble. Maximum value returned is 2048, why? How could I establish maximum on 1024? (without: return ( (n <= 1023) ? ++n : 1024 ) , so proccess should stop when n == 1023 and then, return ++n)
– JuMoGar
Nov 25 '18 at 18:30

@JuMoGar Um, no, the maximum returned is not 2048.
– Swordfish
Nov 25 '18 at 18:54

Yes, It was my fault, a bad printf.... Sorry. And exist any way of maximum returned must be 1024 changing bits operations? There isn't, right?
– JuMoGar
Nov 25 '18 at 19:17

|
show 2 more comments

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Btukfyl