سؤال
أنا فقط حصلت على هذا الإطار ل سودوكو حلالا ، ولكن أنا لا أفهم بناء الجملة التي استخدموها وكيف أنا من المفترض أن المضي قدما.يسمونه بيتسيت ، ولكن عند البحث عنه وجدت شيئا مشابها.
// This file contains a simple implementation of sets of
// digits between 1 and 9, called fields.
#ifndef __SUDOKU_FIELD_H__
#define __SUDOKU_FIELD_H__
#include <iostream>
#include <cassert>
#include "digit.h"
class Field {
private:
// Use integers for a bitset
unsigned int _digits;
// Number of digits in bitset
unsigned int _size;
public:
// Initialize with all digits between 1 and 9 included
Field(void)
: _digits((1 << 1) | (1 << 2) | (1 << 3) |
(1 << 4) | (1 << 5) | (1 << 6) |
(1 << 7) | (1 << 8) | (1 << 9)), _size(9) {}
// Return size of digit set (number of digits in set)
unsigned int size(void) const {
// FILL IN
}
// Test whether digit set is empty
bool empty(void) const {
// FILL IN
}
// Test whether set is assigned (that is, single digit left)
bool assigned(void) const {
// FILL IN
}
// Test whether digit d is included in set
bool in(digit d) const {
assert((d >= 1) && (d <= 9));
// FILL IN
}
// Return digit to which the set is assigned
digit value(void) const {
assert(assigned());
// FILL IN
}
// Print digits still included
void print(std::ostream& os) const;
// Remove digit d from set (d must be still included)
void prune(digit d) {
assert(in(d));
// FILL IN
}
// Assign field to digit d (d must be still included)
void assign(digit d) {
assert(in(d));
// FILL IN
}
};
// Print field
inline std::ostream&
operator<<(std::ostream& os, const Field& f) {
f.print(os); return os;
}
#endif
من الواضح أن / / ملء في هي بالنسبة لي أن أكتب ، ومعنى بيتسيت هو 9 بت حيث يتم تعيين كل منهم في البداية إلى 1.السؤال هو كيف يمكنني التلاعب بها أو استخدامها.
أوه ، بالمناسبة ، هذا رقم:
#ifndef __SUDOKU_DIGIT_H__
#define __SUDOKU_DIGIT_H__
typedef unsigned char digit;
#endif
المحلول
"حقل البت" هو مجرد تفسير لعدد صحيح في الذاكرة كما لو كان عبارة عن قائمة بتات.سوف تقوم بإعداد واختبار وإعادة تعيين البتات في هذا العدد الصحيح بشكل فردي ، وتخبرك التعليقات في الكود بما يجب القيام به في كل وظيفة.
يمكنك استخدام "&" و "|"بالنسبة للبت باستخدام AND و OR ، و "<<" و ">>" لتحويل كل وحدات البت إلى اليسار واليمين.يمكن أن تكون هذه المقالة مفيدة جدًا لك: http://en.wikipedia.org/wiki/Bitwise_operation
نصائح أخرى
هذا التهيئة يحدد البتات 1 - 9 من _digits
إلى 1.التعبير (1 << n)
يعني 1 تحول ن بت إلى اليسار.التعبير a | b
يعني قليلا من الحكمة أو من a
و b
.
لذلك ، بالتفصيل ، كل التعبيرات (1 << n)
يؤدي إلى نمط بت مع جميع الأصفار و 1 في n المركز ال ، إلى عن على 0 < n < 10.كل هذه هي or
'د معا ، لإنتاج بتات نمط بت من 1 إلى 9 مضبوطة على 1:
(1 << 1) 0010 |
(1 << 2) 0100 |
(1 << 3) 1000
======================
1110
(البتات غير المستخدمة غير معروضة)
4 بت:
0000
1 في ثنائي هو:
0001
يستخدم التحول لاختيار بت واحد:
0001 << 0 = 0001 // first bit
0001 << 1 = 0010 // second bit
0001 << 2 = 0100 // third bit
أو يستخدم لتعيين البتات الفردية:
0000 | 0100 = 0100
ويستخدم لاسترداد البتات:
0111 & 0001 = 0001
هذه هي الطريقة التي تعمل بها مجموعات البت.
مثال:
unsigned int x = 0;
x |= 1 << 4; // set 5th bit
x |= 1 << 3; // set 4th bit
x |= 0x3; // set first 2 bits - 0x3 = 0011
unsigned int b = true;
x |= b << 7; // set 8th bit to value of b
if (x & (1 << 2)) { // check if 3rd bit is true
// ...
}
b = (x >> 3) & 1; // set b to value of 4th bit
هنا هو وسيلة لحساب عدد من البتات ، جنبا إلى جنب مع خوارزميات مفيدة أخرى:
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}