fast way to shift bits to positions given in a mask
I am searching for a fast way of iterating over all possible assignments of bits set in a mask.
Example:
mask = 0b10011
result = {0b00000,
0b00001,
0b00010,
0b00011,
0b10000,
0b10001,
0b10010,
0b10011}
I need to iterate over all of them.
Currently I use a similar code to this one, which works well:
int count = popCount(mask);
uint64_t number = 0;
for(uint64_t number = 0; number < (1 << count); ++number)
{
uint64_t result = shiftBits(mask, number, count);
//work with result
//only some light operations
}
// shiftBits(0b10011, 0b101, 3) == 0b10001
// shiftBits(0b10011, 0b111, 3) == 0b10011
// shiftBits(0b10011, 0b000, 3) == 0b00000
uint64_t shiftBits(uint64_t mask, uint64_t number, int count) {
uint64_t result = 0;
for(int i = 0; i < count; ++i)
{
uint64_t least = (mask & ~(mask - 1)); // get uint64_t with only least significant 1 set
uint64_t bitSet = number & uint64_t(1); // check if last bit in number is set
result |= least * bitSet; // if last bit is set, then set corresponding position in result
mask &= mask - 1; // clear lsb set in mask
number = number >> 1; // make 2nd lsb the next one to check
}
return result;
}
Example for shiftBits:
mask = 0b10011001
number = 0b1 01 0 = 0b1010
result = 0b10001000
But I wonder if anyone knows a faster way of performing the operation done in shiftBits, or if there is a faster way of creating this assignments.
Maybe some bitmagic or a way that has no "read after write" and "write after read" conflicts?
c++ bit-manipulation
asked Nov 15 '18 at 18:44
jjjjjj
13910
add a comment |
I am searching for a fast way of iterating over all possible assignments of bits set in a mask.
Example:
mask = 0b10011
result = {0b00000,
0b00001,
0b00010,
0b00011,
0b10000,
0b10001,
0b10010,
0b10011}
I need to iterate over all of them.
Currently I use a similar code to this one, which works well:
int count = popCount(mask);
uint64_t number = 0;
for(uint64_t number = 0; number < (1 << count); ++number)
{
uint64_t result = shiftBits(mask, number, count);
//work with result
//only some light operations
}
// shiftBits(0b10011, 0b101, 3) == 0b10001
// shiftBits(0b10011, 0b111, 3) == 0b10011
// shiftBits(0b10011, 0b000, 3) == 0b00000
uint64_t shiftBits(uint64_t mask, uint64_t number, int count) {
uint64_t result = 0;
for(int i = 0; i < count; ++i)
{
uint64_t least = (mask & ~(mask - 1)); // get uint64_t with only least significant 1 set
uint64_t bitSet = number & uint64_t(1); // check if last bit in number is set
result |= least * bitSet; // if last bit is set, then set corresponding position in result
mask &= mask - 1; // clear lsb set in mask
number = number >> 1; // make 2nd lsb the next one to check
}
return result;
}
Example for shiftBits:
mask = 0b10011001
number = 0b1 01 0 = 0b1010
result = 0b10001000
But I wonder if anyone knows a faster way of performing the operation done in shiftBits, or if there is a faster way of creating this assignments.
Maybe some bitmagic or a way that has no "read after write" and "write after read" conflicts?
c++ bit-manipulation
asked Nov 15 '18 at 18:44
jjjjjj
13910
1
I'm unable to understand whatshiftBits's supposed to do? From the given example, it looks like, the result contains0and all non-zero numbers, whose&with mask equals to not zero. And what doescountrepresent?
– Muhammad Ahmad
Nov 15 '18 at 19:01
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
I don't think you can go faster thanO(k 2^k)where k is the number of set bits to find the result set.
– Mukul Gupta
Nov 15 '18 at 19:43
Is thepdepintrinsic allowed? Only works on modern x86 and is slow on Ryzen
– harold
Nov 15 '18 at 20:24
add a comment |
I am searching for a fast way of iterating over all possible assignments of bits set in a mask.
Example:
mask = 0b10011
result = {0b00000,
0b00001,
0b00010,
0b00011,
0b10000,
0b10001,
0b10010,
0b10011}
I need to iterate over all of them.
Currently I use a similar code to this one, which works well:
int count = popCount(mask);
uint64_t number = 0;
for(uint64_t number = 0; number < (1 << count); ++number)
{
uint64_t result = shiftBits(mask, number, count);
//work with result
//only some light operations
}
// shiftBits(0b10011, 0b101, 3) == 0b10001
// shiftBits(0b10011, 0b111, 3) == 0b10011
// shiftBits(0b10011, 0b000, 3) == 0b00000
uint64_t shiftBits(uint64_t mask, uint64_t number, int count) {
uint64_t result = 0;
for(int i = 0; i < count; ++i)
{
uint64_t least = (mask & ~(mask - 1)); // get uint64_t with only least significant 1 set
uint64_t bitSet = number & uint64_t(1); // check if last bit in number is set
result |= least * bitSet; // if last bit is set, then set corresponding position in result
mask &= mask - 1; // clear lsb set in mask
number = number >> 1; // make 2nd lsb the next one to check
}
return result;
}
Example for shiftBits:
mask = 0b10011001
number = 0b1 01 0 = 0b1010
result = 0b10001000
But I wonder if anyone knows a faster way of performing the operation done in shiftBits, or if there is a faster way of creating this assignments.
Maybe some bitmagic or a way that has no "read after write" and "write after read" conflicts?
c++ bit-manipulation
asked Nov 15 '18 at 18:44
jjjjjj
13910
I am searching for a fast way of iterating over all possible assignments of bits set in a mask.
Example:
mask = 0b10011
result = {0b00000,
0b00001,
0b00010,
0b00011,
0b10000,
0b10001,
0b10010,
0b10011}
I need to iterate over all of them.
Currently I use a similar code to this one, which works well:
int count = popCount(mask);
uint64_t number = 0;
for(uint64_t number = 0; number < (1 << count); ++number)
{
uint64_t result = shiftBits(mask, number, count);
//work with result
//only some light operations
}
// shiftBits(0b10011, 0b101, 3) == 0b10001
// shiftBits(0b10011, 0b111, 3) == 0b10011
// shiftBits(0b10011, 0b000, 3) == 0b00000
uint64_t shiftBits(uint64_t mask, uint64_t number, int count) {
uint64_t result = 0;
for(int i = 0; i < count; ++i)
{
uint64_t least = (mask & ~(mask - 1)); // get uint64_t with only least significant 1 set
uint64_t bitSet = number & uint64_t(1); // check if last bit in number is set
result |= least * bitSet; // if last bit is set, then set corresponding position in result
mask &= mask - 1; // clear lsb set in mask
number = number >> 1; // make 2nd lsb the next one to check
}
return result;
}
Example for shiftBits:
mask = 0b10011001
number = 0b1 01 0 = 0b1010
result = 0b10001000
But I wonder if anyone knows a faster way of performing the operation done in shiftBits, or if there is a faster way of creating this assignments.
Maybe some bitmagic or a way that has no "read after write" and "write after read" conflicts?
c++ bit-manipulation
c++ bit-manipulation
asked Nov 15 '18 at 18:44
jjjjjj
13910
asked Nov 15 '18 at 18:44
jjjjjj
13910
edited Nov 15 '18 at 19:07
jjj
asked Nov 15 '18 at 18:44
jjjjjj
13910
asked Nov 15 '18 at 18:44
jjjjjj
13910
asked Nov 15 '18 at 18:44
jjjjjj
13910
13910
1
I'm unable to understand whatshiftBits's supposed to do? From the given example, it looks like, the result contains0and all non-zero numbers, whose&with mask equals to not zero. And what doescountrepresent?
– Muhammad Ahmad
Nov 15 '18 at 19:01
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
I don't think you can go faster thanO(k 2^k)where k is the number of set bits to find the result set.
– Mukul Gupta
Nov 15 '18 at 19:43
Is thepdepintrinsic allowed? Only works on modern x86 and is slow on Ryzen
– harold
Nov 15 '18 at 20:24
add a comment |
1
I'm unable to understand whatshiftBits's supposed to do? From the given example, it looks like, the result contains0and all non-zero numbers, whose&with mask equals to not zero. And what doescountrepresent?
– Muhammad Ahmad
Nov 15 '18 at 19:01
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
I don't think you can go faster thanO(k 2^k)where k is the number of set bits to find the result set.
– Mukul Gupta
Nov 15 '18 at 19:43
Is thepdepintrinsic allowed? Only works on modern x86 and is slow on Ryzen
– harold
Nov 15 '18 at 20:24
1
1
I'm unable to understand what
shiftBits's supposed to do? From the given example, it looks like, the result contains 0 and all non-zero numbers, whose & with mask equals to not zero. And what does count represent?– Muhammad Ahmad
Nov 15 '18 at 19:01
I'm unable to understand what
shiftBits's supposed to do? From the given example, it looks like, the result contains 0 and all non-zero numbers, whose & with mask equals to not zero. And what does count represent?– Muhammad Ahmad
Nov 15 '18 at 19:01
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
I don't think you can go faster than
O(k 2^k) where k is the number of set bits to find the result set.– Mukul Gupta
Nov 15 '18 at 19:43
I don't think you can go faster than
O(k 2^k) where k is the number of set bits to find the result set.– Mukul Gupta
Nov 15 '18 at 19:43
Is the
pdep intrinsic allowed? Only works on modern x86 and is slow on Ryzen– harold
Nov 15 '18 at 20:24
Is the
pdep intrinsic allowed? Only works on modern x86 and is slow on Ryzen– harold
Nov 15 '18 at 20:24
add a comment |
1 Answer
1
active
oldest
votes
Updated version, replacing the ascending enumeration with an easier expression:
uint64_t i = 0;
do {
// use i
i = (i - mask) & mask;
} while (i);
This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.
No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:
uint64_t i = 0;
do {
// use i
i = ((i | ~mask) + 1) & mask;
} while (i);
It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:
uint64_t i = 0;
do {
i = (i - 1) & mask;
// use i
} while (i);
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53326021%2ffast-way-to-shift-bits-to-positions-given-in-a-mask%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Updated version, replacing the ascending enumeration with an easier expression:
uint64_t i = 0;
do {
// use i
i = (i - mask) & mask;
} while (i);
This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.
No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:
uint64_t i = 0;
do {
// use i
i = ((i | ~mask) + 1) & mask;
} while (i);
It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:
uint64_t i = 0;
do {
i = (i - 1) & mask;
// use i
} while (i);
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
add a comment |
Updated version, replacing the ascending enumeration with an easier expression:
uint64_t i = 0;
do {
// use i
i = (i - mask) & mask;
} while (i);
This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.
No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:
uint64_t i = 0;
do {
// use i
i = ((i | ~mask) + 1) & mask;
} while (i);
It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:
uint64_t i = 0;
do {
i = (i - 1) & mask;
// use i
} while (i);
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
add a comment |
Updated version, replacing the ascending enumeration with an easier expression:
uint64_t i = 0;
do {
// use i
i = (i - mask) & mask;
} while (i);
This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.
No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:
uint64_t i = 0;
do {
// use i
i = ((i | ~mask) + 1) & mask;
} while (i);
It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:
uint64_t i = 0;
do {
i = (i - 1) & mask;
// use i
} while (i);
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
Updated version, replacing the ascending enumeration with an easier expression:
uint64_t i = 0;
do {
// use i
i = (i - mask) & mask;
} while (i);
This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.
No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:
uint64_t i = 0;
do {
// use i
i = ((i | ~mask) + 1) & mask;
} while (i);
It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:
uint64_t i = 0;
do {
i = (i - 1) & mask;
// use i
} while (i);
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
edited Dec 20 '18 at 22:01
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
answered Nov 15 '18 at 20:20
haroldharold
41.8k357109
41.8k357109
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
add a comment |
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
Thanks, I did not think it would be that simple
– jjj
Nov 15 '18 at 20:44
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53326021%2ffast-way-to-shift-bits-to-positions-given-in-a-mask%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
I'm unable to understand what
shiftBits's supposed to do? From the given example, it looks like, the result contains0and all non-zero numbers, whose&with mask equals to not zero. And what doescountrepresent?– Muhammad Ahmad
Nov 15 '18 at 19:01
it moves the least significant bits from number to the positions of the least significant 1s in mask. The positions that are 0 in mask stay 0 in the result.
– jjj
Nov 15 '18 at 19:04
I don't think you can go faster than
O(k 2^k)where k is the number of set bits to find the result set.– Mukul Gupta
Nov 15 '18 at 19:43
Is the
pdepintrinsic allowed? Only works on modern x86 and is slow on Ryzen– harold
Nov 15 '18 at 20:24