divide_by_power_of_two.cpp

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <windows.h>

void divide_by_power_of_two_test1()
{
	for (int n = 0; n < 17; ++n) {
		for (int x = -65536; x <= +65536; ++x) {
			int z = x / (1 << n);

			// https://stackoverflow.com/a/41915393/4699324
			int c2 = (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
			if (z != c2) {
				__debugbreak();
			}
			if (n) {
				// http://joisino.hatenablog.com/entry/2017/09/14/200000
				int c3 = (x + (signed)((unsigned)(x >> 31) >> (32 - n))) >> n;
				if (z != c3) {
					__debugbreak();
				}
			}

		}
	}
}

void divide_by_power_of_two_test2()
{
	int num0 = 4096;
	int num1 = 4096;
	for (int b = -num0; b <= +num0; ++b) {
		for (int a = -num1; a <= +num1; ++a) {
			const int n = 16;
			int x = a * b;
			int c = x / (1 << 16);

#if 0
			auto msg = R"(
　　|ヽ∧＿
　　ゝ ＿＿＼
　　||´・ω・`| ＞　やめなよ
　 /　￣￣　 ､ヽ　__＿＿＿＿＿
　└二⊃　　|∪=|　|───　　／
　　ヽ⊃ー/ノ　　　￣￣￣￣￣
　　　　￣｀´￣
)";
			int sign_a = a >> 31;
			int sign_b = b >> 31;
			int abs_a = (a ^ sign_a) - sign_a;
			int abs_b = (b ^ sign_b) - sign_b;
			int sign_ab = sign_a ^ sign_b;
			int c4 = (abs_a * abs_b * 2) >> 16;
			int c4a = c4 >> 1;
			int c4b = (c4a ^ sign_ab) - sign_ab;
#else
			auto msg = R"(
　 ,j;;;;;j,. ---一､ ｀ 　―--‐､_ l;;;;;;
　｛;;;;;;ゝ T辷iﾌ i 　 　f'辷jァ　 !i;;;;;
　 ヾ;;;ﾊ　　　　ﾉ　　　　　　　.::!lﾘ;;rﾞ
　　 `Z;i　　　〈.,_..,.　　　　　　ﾉ;;;;;;;;>
　 　,;ぇﾊ、　､_,.ｰ-､_',. 　 　,ｆﾞ: Y;;f 　　 そんなふうに考えていた時期が
　　 ~''戈ヽ 　 ｀二´ 　　 r'´:::.　`!　　　俺にもありました
)";
			int c4 = (abs(a) * abs(b) * 2) >> 16; // vqdmulh_n_s16
			int sign_ab = (a ^ b) >> 31;
			int c4a = c4 >> 1;
			int c4b = (c4a ^ sign_ab) - sign_ab;
#endif
			if (c != c4b) {
				MessageBox(NULL, msg, NULL, MB_OK);
				__debugbreak();
			}
		}
	}
}

int main(int argc, char* argv[])
{
	divide_by_power_of_two_test1();
	divide_by_power_of_two_test2();

	return 0;
}