Битовые сдвиги С++
Нужно выполнить путём сдвига вправо все биты, значение которых равно нулю и влево все биты, значение которых равно единице.
Подскажите, как это можно осуществить?
Ответы (3 шт):
Автор решения: vp_arth
→ Ссылка
Это решение основано на том, что в вопросе не указан размер числа.
Поэтому все операции выполняются в рамках исходной ширины входного параметра.
Решение в рамках полной ширины переменной определённого типа проще и есть в соседних(напр. @Qwertiy) ответах.
unsigned solve(unsigned n) {
int zeroes = 0;
unsigned result = 0;
while (n) {
if (n&1) result = (result << 1) | 1; // Вдвигаем единицы
else zeroes++; // Считаем нули
n >>= 1;
}
result <<= zeroes; // Вдвигаем нули
return result;
}
int main()
{
std::cout << solve(1024) << std::endl; // 1024
std::cout << solve(1025) << std::endl; // 1536 = 2^10+2^9
// 10000000001 -> 11000000000
std::cout << solve(682) << std::endl; // 992
// 1010101010 -> 1111100000
std::cout << solve(-1u) << std::endl; // 4294967295
std::cout << solve(0) << std::endl; // 0
}
Или, с шаблонами, концептами и <bit>:
#include <bit>
#include <concepts>
template <std::unsigned_integral T>
T tsolve(const T& n, bool full_width = true) {
T full_bits = ~T{0};
if (n == full_bits || n == 0) {
return n;
}
T t = full_bits;
T shift = (T)(sizeof(T)*8 - std::popcount(n));
if (full_width) {
return t << shift;
}
t >>= shift;
t <<= shift - std::countl_zero(n);
return t;
}
#include <iostream>
int main() {
std::cout.setf(std::ios::hex, std::ios::basefield);
std::cout << tsolve(uint32_t(1033)) << std::endl; // e0000000
std::cout << tsolve(uint16_t(1033)) << std::endl; // e000
std::cout << tsolve(uint32_t(1033), false) << std::endl; // 700
}
Автор решения: Qwertiy
→ Ссылка
#include <stdio.h>
#include <stdint.h>
int main()
{
int x;
scanf("%d", &x);
int n = __builtin_popcount(x);
printf("%08X", n ? ~0U << 32-n : 0);
return 0;
}
Автор решения: user7860670
→ Ссылка
Запостю тогда уж свое решение на C++20 из комментария:
#include <bit>
#include <climits>
#include <cstdint>
[[nodiscard]] constexpr auto
bitsort(::std::uint32_t const value) noexcept
{
if (value)
{
return (compl decltype(value){}) >> (sizeof(value) * CHAR_BIT - ::std::popcount(value));
}
else
{
return value;
}
}
static_assert(0x00 == bitsort(0x00));
static_assert(0x01 == bitsort(0x01));
static_assert(0x01 == bitsort(0x02));
static_assert(0x01 == bitsort(0x02000000));
static_assert(0x03 == bitsort(0x102));
static_assert(0x03 == bitsort(0x01000001));
static_assert(0x00FFFFFF == bitsort(0xFF0FF0FF));
static_assert(0xFFFFFFFF == bitsort(0xFFFFFFFF));